### [P5170 【模板】类欧几里得算法](https://www.luogu.com.cn/problem/P5170) 类欧几里得算法是一种用来统计直线下整点数，以及做从其扩展得来的问题的算法。它的时间复杂度证明与欧几里得算法类似，因此得名。 $$\begin{aligned}f(n,a,b,c)&=\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=\sum_{i=0}^n\left\lfloor\frac{\left(\left\lfloor\frac{a}{c}\right\rfloor c+(a\bmod c)\right)i+\left(\left\lfloor\frac{b}{c}\right\rfloor c+(b\bmod c)\right)}{c}\right\rfloor\\&=\sum_{i=0}^n\left(\left\lfloor\frac{a}{c}\right\rfloor i+\left\lfloor\frac{b}{c}\right\rfloor\right)+\sum_{i=0}^n\left\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\right\rfloor\\&=\frac{n^2+n}{2}\left\lfloor\frac{a}{c}\right\rfloor+(n+1)\left\lfloor\frac{b}{c}\right\rfloor+f(n,a\bmod c,b\bmod c,c)\end{aligned}$$ 将任意问题变成了 $0\le a,b<c$ 的情况。考虑几何意义，横过来数点。记 $m=\left\lfloor\frac{an+b}{c}\right\rfloor$，则式子变为 $$f(n,a,b,c)=\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor=\sum_{i=0}^n\sum_{j=1}^{m}\left[j\le\left\lfloor\frac{ai+b}{c}\right\rfloor\right]$$ 交换求和顺序以缩小问题。