FloorSum - 直線領域の格子点数
(lib/30-math/FloorSum.cpp)

• View this file on GitHub
• Last update: 2023-05-30 04:49:31+09:00

FloorSum

• Σi:[0,n) floor((a*i+b)/m)を計算する

メソッド

• long long FloorSum(long long n, long long m, long long a, long long b)
  • O(log(n+m+a+b))
  • n,m,a,b:はそれぞれ下記に対応
    • $\sum_{i=0}^{n-1} \floor {a*i+b}/m $

参考資料

• Scary Sum - memo
• 格子点の数え上げの高速化 - memo

Verified with

• test/math/FloorSum.test.cpp

Code

/**
 * @title FloorSum - 直線領域の格子点数
 * @docs md/math/FloorSum.md
 */
inline static long long FloorSum(long long n, long long m, long long a, long long b) {
    long long ret=0;
    while(1) {
        if(a >= m) ret += ((n-1)*n*(a/m))>>1,a%=m;
        if(b >= m) ret += n*(b / m),b%=m;
        long long y=(a*n+b)/m, x=(y*m-b);
        if(y==0) return ret;
        ret += (n-(x+a-1)/a)*y;
        b=(a-x%a)%a; swap(a,m); n=y;
    }
}

#line 1 "lib/30-math/FloorSum.cpp"
/**
 * @title FloorSum - 直線領域の格子点数
 * @docs md/math/FloorSum.md
 */
inline static long long FloorSum(long long n, long long m, long long a, long long b) {
    long long ret=0;
    while(1) {
        if(a >= m) ret += ((n-1)*n*(a/m))>>1,a%=m;
        if(b >= m) ret += n*(b / m),b%=m;
        long long y=(a*n+b)/m, x=(y*m-b);
        if(y==0) return ret;
        ret += (n-(x+a-1)/a)*y;
        b=(a-x%a)%a; swap(a,m); n=y;
    }
}

Back to top page