设 \[f\left ( a,b,c,n\right )=\sum_{i=0}^{n}\left \lfloor \frac{ai+b}{c}\right \rfloor\]
当\(\left ( a\geq c\right )\parallel\left ( b\geq c\right )\)时，
\[f\left ( a,b,c,n\right )=\frac{n\left ( n+1\right )}{2}\left \lfloor \frac{a}{c}\right \rfloor+\left ( n+1\right )\left \lfloor \frac{b}{c}\right \rfloor+f\left ( amodc,bmodc,c,n\right )\]
当\(\left ( a< c\right )且\left ( b< c\right )\)时，令\(m=\left \lfloor \frac{an+b}{c}\right \rfloor\)
\[f\left ( a,b,c,n\right )=nm-\left ( c,c-b-1,a,m-1\right )\]
时间复杂度为\(O\left ( logn\right )\)
拓：
1.设\(g\left ( a,b,c,n\right )=\sum_{i=0}^{n}i\left \lfloor \frac{ai+b}{c}\right \rfloor\)
当\(\left ( a\geq c\right )\parallel\left ( b\geq c\right )\)时，
\[g\left ( a,b,c,n\right )=g(amodc,bmodc,c,n)+\frac{n\left ( n+1\right )\left ( 2n+1\right )}{6}\left \lfloor \frac{a}{c}\right \rfloor+\frac{n\left ( n+1\right )}{2}\left \lfloor \frac{b}{c}\right \rfloor\]
当\(\left ( a< c\right )且\left ( b< c\right )\)时，令\(m=\left \lfloor \frac{an+b}{c}\right \rfloor\)
\[g\left ( a,b,c,n\right )=\frac{1}{2}\left [ mn\left ( n+1\right )-h\left ( c,c-b-1,a,m-1\right )-f\left ( c,c-b-1,a,m-1\right )\right ]\]
2.设\(h\left ( a,b,c,n\right )=\sum_{i=0}^{n}\left \lfloor \frac{ai+b}{c}\right \rfloor^{2}\)，
当\(\left ( a\geq c\right )\parallel\left ( b\geq c\right )\)时，
\[h\left ( a,b,c,n\right )=h\left ( amodc,bmodc,c,n\right )+\]
\[+2\left \lfloor \frac{b}{c}\right \rfloor f\left (amodc,bmodc,c,n \right )\]
\[+2\left \lfloor \frac{a}{c}\right \rfloor g\left ( amodc,bmodc,c,n\right )\]
\[+\left \lfloor \frac{a}{c}\right \rfloor^{2}\frac{n\left ( n+1\right )\left ( 2n+1\right )}{6}\]
\[+\left \lfloor \frac{b}{c}\right \rfloor^{2}\left ( n+1\right )\]
\[+\left \lfloor \frac{a}{c}\right \rfloor\left \lfloor \frac{b}{c}\right \rfloor n\left ( n+1\right )\]
当\(\left ( a< c\right )且\left ( b< c\right )\)时，令\(m=\left \lfloor \frac{an+b}{c}\right \rfloor\)
\[h\left ( a,b,c,n\right )=nm\left ( m+1\right )-2g\left ( c,c-b-1,a,m-1\right )-2f\left ( c,c-b-1,a,m-1\right )-f\left ( a,b,c,n\right )\]
模板：
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\n",ans.f,ans.h,ans.g); 63 } 64 return 0; 65 }
对应题目：
原文：https://www.cnblogs.com/wsy107316/p/12809584.html