类欧几里得算法

处理的问题——直线下整点个数：

给出 $a,b,c$ ，求：

$$ \sum_{x=0}^{n-1}\lfloor\frac{ax+b}c\rfloor $$

具体做法

设：

$$ \begin{align} f(a,b,c,n)&=\sum_{x=0}^{n-1}\lfloor\frac{ax+b}c\rfloor\\ &=\sum_{x=0}^{n-1}\lfloor\frac{(a-a\%c)x+(b-b\%c)+a\%cx+b\%c}c\rfloor\\ &=\sum_{x=0}^{n-1}\lfloor\frac{a\%cx+b\%c}c\rfloor+\lfloor\frac ac\rfloor x+\lfloor\frac bc\rfloor\\ &=\frac{n(n-1)}2\lfloor\frac ac\rfloor+n\lfloor\frac bc\rfloor+f(a\%c,b\%c,c,n) \end{align} $$

这时我们发现通过一般推式子的做法已经无法继续优化了，但是类欧几里得给我们提供了一个非常新颖的思路，旋转坐标系：

考虑新的坐标系下的截距和斜率，我们首先计算截距：

$$ \frac{\hat b}{\hat c}=n-x_0 $$

其中 $x_0$ 满足：

$$ \frac {ax_0+b}c=\lfloor\frac{an+b}c\rfloor $$

最后得到：

$$ \frac{\hat b}{\hat c}=\frac{(an+b)\%c}{a} $$

然后计算循环上界，这个显然是 $\lfloor\frac{an+b}c\rfloor$ 。

然后再考虑计算斜率，稍微推一下就会发现是 $\frac ca$ 。

于是我们就的到了一个这样的式子：

$$ f(a,b,c,n)=f(c,(an+b)\%c,a,(an+b)/c) $$

把这个带回原始，我们就的到了最终的式子：

$$ f(a,b,c,n)=\frac{n(n-1)}2\lfloor\frac ac\rfloor+n\lfloor\frac bc\rfloor+f(c,(a\%c\times n+b\%c)\%c,a\%c,(a\%c\times n+b\%c)/c) $$