当我们要计算形如
[ sum_{i=0}^nlfloor frac{ai+b}{c}
floor
]
且a，b>=0,c>0时
可以使用类欧算法。
首先有以下公式
[lceil frac{a}{b}
ceil = lfloor frac{a+b-1}{b}
floor
]
[lfloorfrac{a}{b}
floor = lceil frac{a-b+1}{b}
ceil
]
挺容易推的：关于1式，如果 a % b != 0,那么右边就会比左边大1，2式原理相同。
然后开始推（？
我们令
[F(a,b,c,n)=sum_{i=0}^nlfloor frac{ai+b}{c}
floor
]
[{a}geq{c}Rightarrowsum_{i=0}^nlfloor frac{ai+b}{c}
floor=sum_{i=0}^n(lfloor frac{a\%c imes i+b}{c}
floor+lfloorfrac{a}{c}
floor i)=sum_{i=0}^nlfloor frac{a\%c imes i+b}{c}
floor+lfloorfrac{a}{c}
floorfrac{n imes (n+1)}{2}
]
[{b}geq{c}Rightarrowsum_{i=0}^nlfloor frac{ai+b}{c}
floor=sum_{i=0}^nlfloor frac{a i+b\% c}{c}
floor+lfloorfrac{b}{c}
floor(n+1)
]
因此
[{a}geq{c}||{b}geq{c}Rightarrowsum_{i=0}^nlfloor frac{ai+b}{c}
floor=sum_{i=0}^nlfloor frac{(a\%c) i+b\% c}{c}
floor+lfloorfrac{b}{c}
floor(n+1)+lfloorfrac{a}{c}
floorfrac{n imes (n+1)}{2}
]
[Rightarrow F(a,b,c,n) = F(a\%c,b\%c,c,n)++lfloorfrac{b}{c}
floor(n+1)+lfloorfrac{a}{c}
floorfrac{n imes (n+1)}{2}
]
之后只要解决(a lt c && blt c)的情况就好了（？
由
[sum_{i=0}^nlfloor frac{ai+b}{c}
floor
=sum_{i=0}^nsum_{j=1}^{lfloor frac{ai+b}{c}
floor}1
=sum_{i=0}^nsum_{j=1}^{lfloor frac{an+b}{c}
floor}[{jleq lfloor frac{ai+b}{c}
floor}]
]
交换求和顺序（
[Rightarrow sum_{j=1}^{lfloor frac{an+b}{c}
floor}sum_{i=0}^n[{jleq lfloor frac{ai+b}{c}
floor}]
]
又有
[lfloor frac{a}{b}
floor geq c Leftrightarrow ageq bc
]
[lceil frac{a}{b}
ceil leq c Leftrightarrow aleq bc
]
因此
[=sum_{j=1}^{lfloor frac{an+b}{c}
floor}sum_{i=0}^n[jcleq {ai+b}]
=sum_{j=1}^{lfloor frac{an+b}{c}
floor}sum_{i=0}^n[lceil frac{jc-b}{a}
ceil leq i]
=sum_{j=1}^{lfloor frac{an+b}{c}
floor}[n+1-lceil frac{jc-b}{a}
ceil]
]
[=sum_{j=1}^{lfloor frac{an+b}{c}
floor}[n+1-lfloor frac{jc-b+a-1}{a}
floor]
]
[=nlfloor frac{an+b}{c}
floor-sum_{j=1}^{lfloor frac{an+b}{c}
floor}[lfloor frac{jc-b+a-1}{a}
floor-1]
=nlfloor frac{an+b}{c}
floor-sum_{j=0}^{lfloor frac{an+b}{c}
floor-1}[lfloor frac{(j+1)c-b-1}{a}
floor]
]
因此我们有(a,blt c)时
[F(a,b,c,n)=nlfloor frac{an+b}{c}
floor-F(c,-1-b+c,a,lfloor frac{an+b}{c}
floor-1)
]
然后就 可以递归了 终止条件a=0
以下代码
ll exgcd(ll a, ll b, ll c, ll n){
if(a==0) return (n+1)*(b/c);
if(a>=c||b>=c) return exgcd(a%c, b%c, c, n) + floor(a/c)*n*(n+1)/2 + floor(b/c)*(n+1);
ll temp = (a*n+b)/c;
return n*temp - exgcd(c, c-b-1, a, temp-1);
}