用途
计算函数求和, 形如
[f(a,b,c,n)=sum_{i=0}^{n}lfloor frac{ai+b}{c}
floor
]
过程
当 (a ge c) 或 (b ge c) 时,
[f(a,b,c,n)=frac{n(n+1)}{2}*lfloor frac{a}{c}
floor + (n+1)* lfloor frac{b}{c}
floor + f(a mod c,b mod c,c,n).
]
当 (a < c) 并且 (b < c) 时,
设 $ m=lfloor frac{an+b}{c}
floor, $
[f(a,b,c,n)=mn-f(c,c-b-1,a,m-1).
]
递归处理直到 $ a=0 $ 即可.
例题
数形结合, 把式子稍微转换一下, 套用类欧几里得算法即可.