类欧几里得算法
基础
求
[f(a,b,c,n)=sum_{i=0}^n leftlfloor dfrac{ai+b}{c}
ight
floor
]
(age c)或(bge c)
[egin{aligned}
f(a,b,c,n)&=sum_{i=0}^n leftlfloor dfrac{ai+b}{c}
ight
floor\
&=sum_{i=0}^n leftlfloor dfrac{cleftlfloorfrac{a}{c}
ight
floor i+amod c imes i+cleftlfloorfrac{b}{c}
ight
floor+bmod c}{c}
ight
floor\
&=sum_{i=0}^nleftlfloordfrac{a}{c}
ight
floor i+leftlfloorfrac{b}{c}
ight
floor+leftlfloor dfrac{amod c imes i+bmod c}{c}
ight
floor\
&=leftlfloordfrac{a}{c}
ight
floordfrac{n(n+1)}{2}+leftlfloordfrac{b}{c}
ight
floor(n+1)+f(amod c,bmod c,c,n)
end{aligned}
]
(a<c)且(b<c)
把(leftlfloor dfrac{ai+b}{c} ight floor)替换为(sumlimits_{j=0}left[ j<leftlfloor dfrac{ai+b}{c} ight floor ight])，其中(j)的上界为(leftlfloor dfrac{an+b}{c} ight floor-1)。也就是求
[f(a,b,c,n)=sum_{i=0}^nsum_{j=0}left[j<leftlfloor dfrac{ai+b}{c}
ight
floor
ight]
]
交换求和号
[f(a,b,c,d)=sum_{j=0}^{lfloorfrac{an+b}{c}
floor-1}sum_{i=0}^nleft[j<leftlfloordfrac{ai+b}{c}
ight
floor
ight]\
]
乱搞一下后面那个东西，通过下取整与不等号的变换把(i)搞掉
[j<leftlfloordfrac{ai+b}{c}
ight
floor Leftrightarrow j+1le leftlfloordfrac{ai+b}{c}
ight
floorLeftrightarrow j+1le dfrac{ai+b}{c}\
Leftrightarrow dfrac{cj+c-b}{a}le i Leftrightarrow ige dfrac{cj+c-b}{a}Leftrightarrow i>leftlfloordfrac{cj+c-b-1}{a}
ight
floor
]
而(i)的上界是确定的，为(n)，也就是说(j<leftlfloordfrac{ai+b}{c} ight floor)的(i)的个数等于(n-leftlfloordfrac{cj+c-b-1}{a} ight floor)。
[egin{aligned}
f(a,b,c,d)&=sum_{j=0}^{lfloor frac{an+b }{c}
floor-1}sum_{i=0}^nleft[j<leftlfloordfrac{ai+b}{c}
ight
floor
ight]\
&=sum_{j=0}^{lfloor frac{an+b }{c}
floor-1}n-leftlfloordfrac{cj+c-b-1}{a}
ight
floor\
&= leftlfloordfrac{an+b}{c}
ight
floor n-sum_{j=0}^{lfloorfrac{an+b}{c}
floor-1}leftlfloordfrac{cj+c-b-1}{a}
ight
floor\
&= leftlfloordfrac{an+b}{c}
ight
floor n-f(c,c-b-1,a,lfloorfrac{an+b}{c}
floor -1)
end{aligned}
]
以后方便起见记(leftlfloordfrac{an+b}{c} ight floor=m)，记(leftlfloordfrac{cj+c-b-1}{a} ight floor=t)，即
[f(a,b,c,n)=mn-f(c,c-b-1,a,m-1)
]
递归求解即可，边界为(a=0)
复杂度(O(log n))，证明类似欧几里得算法，故算法得名
扩展
求
[g(a,b,c,n)=sum_{i=0}^n ileftlfloor dfrac{ai+b}{c}
ight
floor\
h(a,b,c,n)=sum_{i=0}^n leftlfloor dfrac{ai+b}{c}
ight
floor^2
]
求(g(a,b,c,n))
(age c)或(bge c)
[egin{aligned}
g(a,b,c,n)&=sum_{i=0}^n ileftlfloor dfrac{ai+b}{c}
ight
floor\
&=sum_{i=0}^n ileftlfloor dfrac{cleftlfloorfrac{a}{c}
ight
floor i+amod c imes i+cleftlfloorfrac{b}{c}
ight
floor+bmod c}{c}
ight
floor\
&=sum_{i=0}^nleftlfloordfrac{a}{c}
ight
floor i^2+leftlfloorfrac{b}{c}
ight
floor i+leftlfloor dfrac{amod c imes i+bmod c}{c}
ight
floor i\
&=leftlfloordfrac{a}{c}
ight
floordfrac{n(n+1)(2n+1)}{6}+leftlfloordfrac{b}{c}
ight
floordfrac{n(n+1)}{2}+g(a\% c,b\% c,c,n)
end{aligned}
]
(a<c)且(b<c)
(m=leftlfloordfrac{an+b}{c} ight floor)，(t=leftlfloordfrac{cj+c-b-1}{a} ight floor)
[egin{aligned}
g(a,b,c,n)&=sum_{i=0}^nisum_{j=0}left[j<leftlfloor dfrac{ai+b}{c}
ight
floor
ight]\
&=sum_{j=0}^{m-1}sum_{i=0}^nileft [j<leftlfloordfrac{ai+b}{c}
ight
floor
ight]\
&=sum_{j=0}^{m-1}sum_{i=0}^ni [i>t]\
&=sum_{j=0}^{m-1}frac{n(n+1)}{2}-frac{t(t+1)}{2}\
&=dfrac{1}{2}[mn(n+1)-sum_{j=0}^{m-1}t^2-sum_{j=0}^{m-1}t ]\
&=dfrac{1}{2}[mn(n+1)-h(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1) ]
end{aligned}
]
递归边界：(a=0)
求(h(a,b,c,n))
(age c)或(bge c)
[egin{aligned}
h(a,b,c,n)&=sum_{i=0}^n leftlfloor dfrac{ai+b}{c}
ight
floor^2\
&=sum_{i=0}^nleft(leftlfloordfrac{a}{c}
ight
floor i+leftlfloorfrac{b}{c}
ight
floor +leftlfloor dfrac{amod c imes i+bmod c}{c}
ight
floor
ight)^2 \
&=sum_{i=0}^nleftlfloordfrac{a}{c}
ight
floor^2 i^2+leftlfloorfrac{b}{c}
ight
floor^2 +leftlfloor dfrac{a \% c imes i+b\% c}{c}
ight
floor^2+2leftlfloordfrac{a}{c}
ight
floorleftlfloorfrac{b}{c}
ight
floor i\& +2leftlfloordfrac{a}{c}
ight
floorleftlfloor dfrac{a\% c imes i+b\% c}{c}
ight
floor i+2leftlfloordfrac{b}{c}
ight
floorleftlfloor dfrac{a\% c imes i+b\% c}{c}
ight
floor\
&=frac{n(n+1)(2n+1)}{6}leftlfloordfrac{a}{c}
ight
floor^2+(n+1)leftlfloorfrac{b}{c}
ight
floor^2+n(n+1)leftlfloordfrac{a}{c}
ight
floorleftlfloorfrac{b}{c}
ight
floor+2leftlfloordfrac{a}{c}
ight
floor g(a\% c,b\%c,c,n)\
& +2leftlfloordfrac{b}{c}
ight
floor f(a\%c,b\%c,c,n)+h(a\%c,b\%c,c,n)
end{aligned}
]
(a<c)且(b<c)
(m=leftlfloordfrac{an+b}{c} ight floor)，(t=leftlfloordfrac{cj+c-b-1}{a} ight floor)
[h(a,b,c,n)=sum_{i=0}^n leftlfloor dfrac{ai+b}{c}
ight
floor^2
]
将(n^2)写成(left(2sumlimits_{i=1}^n i ight)-n)
[egin{aligned}
h(a,b,c,n)&=sum_{i=0}^nleft(2sum_{j=1}^{leftlfloor frac{ai+b}{c}
ight
floor}j
ight)-leftlfloor dfrac{ai+b}{c}
ight
floor\
&=left(2sum_{i=0}^nsum_{j=0}^{leftlfloor frac{ai+b}{c}
ight
floor-1}j+1
ight)-f(a,b,c,n)\
&=left(2sum_{j=0}^{m-1}sum_{i=0}^n (j+1)left[j< leftlfloor frac{ai+b}{c}
ight
floor
ight]
ight)-f(a,b,c,n)
end{aligned}
]
其中
[egin{aligned}
sum_{j=0}^{m-1}sum_{i=0}^n (j+1)left[j< leftlfloor frac{ai+b}{c}
ight
floor
ight]&=sum_{j=1}^{m-1}(j+1)sum_{i=0}^n left[j< leftlfloor frac{ai+b}{c}
ight
floor
ight]\
&=sum_{j=0}^{m-1}(j+1)sum_{i=0}^n[i>t]\
&=sum_{j=0}^{m-1}(j+1)(n-t)\
&=dfrac{m(m+1)}{2}n-f(c,c-b-1,a,m-1) -g(c,c-b-1,a,m-1)
end{aligned}
]
所以
[egin{aligned}
h(a,b,c,n)&=m(m+1)n-2f(c,c-b-1,a,m-1)-2g(c,c-b-1,a,m-1)-f(a,b,c,n)
end{aligned}
]
递归边界：(a=0)
实现注意事项
因为(g,h)有相互调用，递归时把一组((a,b,c,n))的(f,g,h)都求出来