发布时间：2025-05-22

类欧几里得推导

求 $f(a,b,c,n)=\sum_{i=0}^{n-1}\lfloor \frac{ai+b}{c} \rfloor$

若 $a \geq c$ 或者 $b \geq c$ ,令 $a'=a \mod c,b'=b \mod c$

f(a,b,c,n)=\sum_{i=0}^{n-1} \lfloor \frac{a}{c} \rfloor i+\lfloor \frac{b}{c} \rfloor+\lfloor \frac{a'i+b'}{c} \rfloor=\frac{n(n-1)}{2}\lfloor \frac{a}{c} \rfloor+n\lfloor \frac{b}{c} \rfloor+f(a',b',c,n)

就转化成了 $a \lt c,b \lt c$ 的情况

考虑 $a \lt c,b \lt c$ 的情况：

f(a,b,c,n)=\sum_{i=0}^{n-1}\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1}[1]

令 $m=\lfloor\frac{a(n-1)+b}{c} \rfloor-1$

f(a,b,c,n)=\sum_{j=0}^m\sum_{i=0}^{n-1}[j \lt \lfloor \frac{ai+b}{c} \rfloor]\\ =\sum_{j=0}^{m-1}\sum_{i=0}^{n-1}[c(j+1) \leq ai+b]\\ =\sum_{j=0}^{m-1}\sum_{i=0}^{n-1}[i \gt \lfloor \frac{cj+c-b-1}{a}\rfloor]\\ =\sum_{j=0}^{m-1}[n-1-\lfloor \frac{cj+c-b-1}{a}\rfloor]\\ =(n-1)m-f(c,c-b-1,a,m)

复杂度 $O(\log \max(a,c))$

从几何意义讲，表示的是 $y=\frac{ax+b}{c}$ 下的整数点

类似地， $g(a,b,c,n)=\sum_{i=0}^{n-1}i\lfloor \frac{ai+b}{c} \rfloor,h(a,b,c,n)=\sum_{i=0}^{n-1}\lfloor \frac{ai+b}{c} \rfloor^2$

$a \geq c,b \geq c$ 的情况:

$g(a,b,c,n)=\frac{n(n-1)(2n-1)}{6}\lfloor \frac{a}{c} \rfloor+\frac{n(n-1)}{2}\lfloor\frac{b}{c}\rfloor+g(a',b',c,n)$

$h(a,b,c,n)=h(a',b',c,n)+2\lfloor \frac{a}{c} \rfloor g(a',b',c,n)+2\lfloor\frac{b}{c}\rfloor f(a',b',c,n)+\frac{n(n-1)(2n-1)}{6}\lfloor \frac{a}{c} \rfloor^2+n(n-1)\lfloor \frac{a}{c} \rfloor \lfloor \frac{b}{c} \rfloor+n\lfloor\frac{b}{c}\rfloor^2$

$a \lt c,b \lt c$ 的情况：

$g(a,b,c,n)=\frac{1}{2}(mn(n-1)-h(c,c-b-1,a,m)-f(c,c-b-1,a,m))$

$h(a,b,c,n)=(n-1)m^2-2g(c,c-b-1,a,m)-f(c,c-b-1,a,m)$

cpp

struct FloorSum{
    static constexpr int MOD=998244353,inv2=499122177,inv6=166374059;
    struct Node{
        int f=0,g=0,h=0;
    };
    int mo(int x){return x>=MOD?x-MOD:x;}
    int sqr(int x){return 1ll*x*x%MOD;}
    Node f(int a,int b,int c,int n){
        Node res;
        if(!a){
            res.f=1ll*b/c*n%MOD;
            res.g=1ll*n*(n-1)/2%MOD*(b/c)%MOD;
            res.h=1ll*sqr(b/c)*n%MOD;
        }
        else if(a>=c||b>=c){
            Node o=f(a%c,b%c,c,n);
            res.f=(o.f+1ll*n*(n-1)/2%MOD*(a/c)+1ll*b/c*n)%MOD;
            res.g=(o.g+1ll*a/c*n%MOD*(n-1)%MOD*(n*2-1)%MOD*inv6+1ll*n*(n-1)/2%MOD*(b/c))%MOD;
            res.h=(o.h+2ll*(a/c)*o.g+2ll*(b/c)*o.f+1ll*n*(n-1)%MOD*(n*2-1)%MOD*inv6%MOD*sqr(a/c)+1ll*n*(n-1)%MOD*(a/c)%MOD*(b/c)+1ll*n*sqr(b/c))%MOD;
        }
        else{
            int m=(1ll*a*(n-1)+b)/c;
            Node o=f(c,c-b-1,a,m);
            res.f=(1ll*(n-1)*m-o.f+MOD)%MOD;
            res.g=((1ll*m*n%MOD*(n-1)-o.h-o.f)%MOD+MOD)*inv2%MOD;
            res.h=(1ll*(n-1)*m%MOD*m-mo(o.g*2)-o.f+MOD+MOD)%MOD;
        }
        return res;
    }
};
void solve(){
    FloorSum f;
    int a,b,c,n;
    cin>>n>>a>>b>>c;
    auto res=f.f(a,b,c,n+1);
    cout<<res.f<<" "<<res.h<<" "<<res.g<<"\n";
}

类欧几里得推导 ​

类欧几里得推导