Sum of Floor of Linear(一次関数の床関数の和) (math/number-theory/sum-of-floor-of-linear.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "math/number-theory/sum-of-floor-of-linear.hpp"

sum_of_floor_of_linear

T sum_of_floor_of_linear(const T &n, const T &m, T a, T b)

$\displaystyle \sum_{i=0}^{n-1} \textrm{floor}{(\frac {a \times i + b} {m})}$ を返します。

制約

• $1 \le n, m$
• $0 \leq a, b \leq m$

計算量

• $O(\log (n + m + a + b))$

Verified with

• test/verify/yosupo-sum-of-floor-of-linear.test.cpp

Code

template <typename T>
T sum_of_floor_of_linear(const T &n, const T &m, T a, T b) {
  T ret = 0;
  if (a >= m) ret += (n - 1) * n * (a / m) / 2, a %= m;
  if (b >= m) ret += n * (b / m), b %= m;
  T y = (a * n + b) / m;
  if (y == 0) return ret;
  T x = y * m - b;
  ret += (n - (x + a - 1) / a) * y;
  ret += sum_of_floor_of_linear(y, a, m, (a - x % a) % a);
  return ret;
}

#line 1 "math/number-theory/sum-of-floor-of-linear.hpp"
template <typename T>
T sum_of_floor_of_linear(const T &n, const T &m, T a, T b) {
  T ret = 0;
  if (a >= m) ret += (n - 1) * n * (a / m) / 2, a %= m;
  if (b >= m) ret += n * (b / m), b %= m;
  T y = (a * n + b) / m;
  if (y == 0) return ret;
  T x = y * m - b;
  ret += (n - (x + a - 1) / a) * y;
  ret += sum_of_floor_of_linear(y, a, m, (a - x % a) % a);
  return ret;
}

Back to top page