类欧几里得算法

问题描述

对于给定 \(0\le b<c,0\le c,n\le 10^9\) ，在 \(O(\log N)\) 时间内求：

\[ f(n,a,b,c)=\sum_{i=0}^n\left\lfloor\frac{ia+b}{c}\right\rfloor \]

Floor Sum

通过类欧几里得算法实现。

具体见OI-wiki

例题ABC283EX

题目描述

给定 \(0\le R<M,0\le M,N\le 10^9\) ，求下式：

\[ \sum_{i=0}^{N}\text{popcount}(i)\cdot[i\bmod M=R] \]

多测 \(T\le10^5\) 。

解答

注意到一个数 \(A\) 在第 \(k\) 位上的值等价于：

\[ \left\lfloor\frac{A+2^k}{2^{k+1}}\right\rfloor-\left\lfloor\frac{A}{2^{k+1}}\right\rfloor \]

于是有：

\[ \begin{aligned} &\sum_{i=0}^{N}\text{popcount}(i)\cdot[i\bmod M=R]\\ &=\sum_{i=0}^{\lfloor\frac{N-R}{M}\rfloor}\text{popcount}(iM+R)\\ &=\sum_{i=0}^{\lfloor\frac{N-R}{M}\rfloor}\sum_{k=0}^{30}\left\lfloor\frac{iM+R+2^k}{2^{k+1}}\right\rfloor-\left\lfloor\frac{iM+R}{2^{k+1}}\right\rfloor\\ &=\sum_{k=0}^{30}\sum_{i=0}^{\lfloor\frac{N-R}{M}\rfloor}\left\lfloor\frac{iM+R+2^k}{2^{k+1}}\right\rfloor-\left\lfloor\frac{iM+R}{2^{k+1}}\right\rfloor\\ &=\sum_{k=0}^{30}f\left(\left\lfloor\frac{N-R}{M}\right\rfloor,M,R+2^k,2^{k+1}\right)-f\left(\left\lfloor\frac{N-R}{M}\right\rfloor,M,R,2^{k+1}\right)\\ \end{aligned} \]

上述式子可在 \(O(\log^2N)\) 时间下求出，可以通过。

Floor Sum Template

// sigma i = 0 to n-1: floor((ai+b)/m)
long long floor_sum(long long n, long long m, long long a, long long b) {
    long long ans = 0;
    if (a >= m) {
        ans += (n - 1) * n * (a / m) / 2;
        a %= m;
    }
    if (b >= m) {
        ans += n * (b / m);
        b %= m;
    }

    long long y_max = (a * n + b) / m, x_max = (y_max * m - b);
    if (y_max == 0) return ans;
    ans += (n - (x_max + a - 1) / a) * y_max;
    ans += floor_sum(y_max, a, m, (a - x_max % a) % a);
    return ans;
}

来自Atcoder Library