设 [fleft ( a,b,c,n ight )=sum_{i=0}^{n}left lfloor frac{ai+b}{c} ight floor]
当(left ( ageq c ight )parallelleft ( bgeq c ight ))时，
[fleft ( a,b,c,n ight )=frac{nleft ( n+1 ight )}{2}left lfloor frac{a}{c} ight floor+left ( n+1 ight )left lfloor frac{b}{c} ight floor+fleft ( amodc,bmodc,c,n ight )]
当(left ( a< c ight )且left ( b< c ight ))时，令(m=left lfloor frac{an+b}{c} ight floor)
[fleft ( a,b,c,n ight )=nm-left ( c,c-b-1,a,m-1 ight )]
时间复杂度为(Oleft ( logn ight ))
拓：
1.设(gleft ( a,b,c,n ight )=sum_{i=0}^{n}ileft lfloor frac{ai+b}{c} ight floor)
当(left ( ageq c ight )parallelleft ( bgeq c ight ))时，
[gleft ( a,b,c,n ight )=g(amodc,bmodc,c,n)+frac{nleft ( n+1 ight )left ( 2n+1 ight )}{6}left lfloor frac{a}{c} ight floor+frac{nleft ( n+1 ight )}{2}left lfloor frac{b}{c} ight floor]
当(left ( a< c ight )且left ( b< c ight ))时，令(m=left lfloor frac{an+b}{c} ight floor)
[gleft ( a,b,c,n ight )=frac{1}{2}left [ mnleft ( n+1 ight )-hleft ( c,c-b-1,a,m-1 ight )-fleft ( c,c-b-1,a,m-1 ight ) ight ]]
2.设(hleft ( a,b,c,n ight )=sum_{i=0}^{n}left lfloor frac{ai+b}{c} ight floor^{2})，
当(left ( ageq c ight )parallelleft ( bgeq c ight ))时，
[hleft ( a,b,c,n ight )=hleft ( amodc,bmodc,c,n ight )+]
[+2left lfloor frac{b}{c} ight floor fleft (amodc,bmodc,c,n ight )]
[+2left lfloor frac{a}{c} ight floor gleft ( amodc,bmodc,c,n ight )]
[+left lfloor frac{a}{c} ight floor^{2}frac{nleft ( n+1 ight )left ( 2n+1 ight )}{6}]
[+left lfloor frac{b}{c} ight floor^{2}left ( n+1 ight )]
[+left lfloor frac{a}{c} ight floorleft lfloor frac{b}{c} ight floor nleft ( n+1 ight )]
当(left ( a< c ight )且left ( b< c ight ))时，令(m=left lfloor frac{an+b}{c} ight floor)
[hleft ( a,b,c,n ight )=nmleft ( m+1 ight )-2gleft ( c,c-b-1,a,m-1 ight )-2fleft ( c,c-b-1,a,m-1 ight )-fleft ( a,b,c,n ight )]
模板：
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <string> 6 using namespace std; 7 typedef long long ll; 8 const int maxn = 1e5+10; 9 const int mod = 998244353; 10 const int inf = 0x3f3f3f3f; 11 #define rep(i,first,second) for(ll i=first;i<=second;i++) 12 #define dep(i,first,second) for(ll i=first;i>=second;i--) 13 14 int n,a,b,c; 15 int inv2=499122177,inv6=166374059; 16 17 struct data{ 18 int f,g,h; //f=∑(ai+b)/c g=∑i*(ai+b)/c h=∑((ai+b)/c)^2 (0<=i<=n) 19 }; 20 21 data calc(int n,int a,int b,int c){ 22 int ac=a/c, bc=b/c, m=(1ll*a*n+b)/c, n1=n+1, n21=n*2+1; 23 data d; 24 if( a==0 ){ 25 d.f=1ll*bc*n1%mod; 26 d.g=1ll*bc*n%mod*n1%mod*inv2%mod; 27 d.h=1ll*bc*bc%mod*n1%mod; 28 return d; 29 } 30 31 if( a>=c || b>=c ){ 32 d.f=(1ll*n*n1%mod*inv2%mod*ac%mod + 1ll*bc*n1%mod)%mod; 33 d.g=(1ll*ac*n%mod*n1%mod*n21%mod*inv6%mod + 1ll*bc*n%mod*n1%mod*inv2%mod)%mod; 34 d.h=((1ll*ac*ac%mod*n%mod*n1%mod*n21%mod*inv6%mod + 35 1ll*bc*bc%mod*n1%mod)%mod+ 36 1ll*ac*bc%mod*n%mod*n1%mod)%mod; 37 38 data e=calc(n,a%c,b%c,c); 39 40 d.h = (d.h+((e.h + 2*1ll*bc%mod*e.f%mod)%mod + 2*1ll*ac%mod*e.g%mod)%mod)%mod; 41 d.g = (d.g+e.g)%mod; 42 d.f = (d.f+e.f)%mod; 43 44 return d; 45 } 46 47 data e=calc(m-1,c,c-b-1,a); 48 d.f=(1ll*n*m%mod-e.f+mod)%mod; 49 d.g=(((1ll*n*m%mod*n1%mod-e.h-e.f)%mod*inv2)%mod+mod)%mod; 50 d.h=((1ll*n*m%mod*(m+1)%mod-2*e.g%mod-2*e.f%mod-d.f)%mod+mod)%mod; 51 return d; 52 } 53 54 signed main() 55 { 56 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 57 int t; 58 scanf("%d",&t); 59 while( t-- ){ 60 scanf("%d%d%d%d",&n,&a,&b,&c); 61 data ans=calc(n,a,b,c); 62 printf("%d %d %d ",ans.f,ans.h,ans.g); 63 } 64 return 0; 65 }
对应题目：