sum of floor of linear
(include/emthrm/math/floor_sum.hpp)

• View this file on GitHub
• Last update: 2022-12-15 22:18:37+09:00
• Include: #include "emthrm/math/floor_sum.hpp"

\[\sum_{i = 0}^{N - 1} \left\lfloor \frac{Ai + B}{M} \right\rfloor\]

時間計算量

$O(\log{M})$

仕様

名前	戻り値	要件
long long floor_sum(long long a, long long b, long long m, long long n);	$\sum_{i = 0}^{N - 1} \left\lfloor \frac{Ai + B}{M} \right\rfloor$	$M \in \mathbb{N}^+$

参考文献

• https://rsk0315.hatenablog.com/entry/2020/12/13/231307
• https://qiita.com/R_olldIce/items/3e2c80baa6d5e6f3abe9#4-floor_sum
• https://github.com/atcoder/ac-library/blob/c8e527063415e2f9aaf87cf80f2c59730a46ed98/atcoder/math.hpp#L82-L97
• https://github.com/atcoder/ac-library/blob/6c88a70c8f95fef575af354900d107fbd0db1a12/atcoder/internal_math.hpp#L180-L207

Submissons

https://judge.yosupo.jp/submission/39036

Verified with

• 数学/sum of floor of linear (test/math/floor_sum.test.cpp)

Code

#ifndef EMTHRM_MATH_FLOOR_SUM_HPP_
#define EMTHRM_MATH_FLOOR_SUM_HPP_

#include <utility>

namespace emthrm {

long long floor_sum(long long a, long long b, long long m, long long n) {
  long long res = 0;
  if (a < 0) {
    long long nxt_a = a % m;
    if (nxt_a < 0) nxt_a += m;
    res -= n * (n - 1) / 2 * ((nxt_a - a) / m);
    a = nxt_a;
  }
  if (b < 0) {
    long long nxt_b = b % m;
    if (nxt_b < 0) nxt_b += m;
    res -= n * ((nxt_b - b) / m);
    b = nxt_b;
  }
  while (true) {
    if (a >= m) {
      res += n * (n - 1) / 2 * (a / m);
      a %= m;
    }
    if (b >= m) {
      res += n * (b / m);
      b %= m;
    }
    const long long y_max = a * n + b;
    if (y_max < m) break;
    b = y_max % m;
    n = y_max / m;
    std::swap(a, m);
  }
  return res;
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_FLOOR_SUM_HPP_

#line 1 "include/emthrm/math/floor_sum.hpp"



#include <utility>

namespace emthrm {

long long floor_sum(long long a, long long b, long long m, long long n) {
  long long res = 0;
  if (a < 0) {
    long long nxt_a = a % m;
    if (nxt_a < 0) nxt_a += m;
    res -= n * (n - 1) / 2 * ((nxt_a - a) / m);
    a = nxt_a;
  }
  if (b < 0) {
    long long nxt_b = b % m;
    if (nxt_b < 0) nxt_b += m;
    res -= n * ((nxt_b - b) / m);
    b = nxt_b;
  }
  while (true) {
    if (a >= m) {
      res += n * (n - 1) / 2 * (a / m);
      a %= m;
    }
    if (b >= m) {
      res += n * (b / m);
      b %= m;
    }
    const long long y_max = a * n + b;
    if (y_max < m) break;
    b = y_max % m;
    n = y_max / m;
    std::swap(a, m);
  }
  return res;
}

}  // namespace emthrm

Back to top page