类欧几里得算法

一直用一直拷板...需要补一补了。

问题

\[ f(a,b,c,n)=\sum_{i=0}^n \lfloor \frac {ai+b} c \rfloor \]

即在一条直线下的整点数.

做法

如果 \(a \ge c\)\(b \ge c\),则 \(f(a,b,c,n) = \frac {n(n+1)}2\lfloor \frac a c \rfloor + (n+1) \lfloor \frac {b} {c}\rfloor + f(a\bmod c,b\bmod c,c,n)\)

否则 \[ f(a,b,c,n)=\sum_{i=0}^n \lfloor \frac {ai+b} c \rfloor \\ =\sum_{x \ge 0} \sum_{i=0}^n [x < \lceil \frac{ai+b} c \rceil]\\ =\sum_{x \ge 0} \sum_{i=0}^n [xc < ai+b+c-1]\\ =\sum_{x \ge 0} \sum_{i \le n} [i > \lfloor \frac{xc-b-c+1} a\rfloor]\\ =\sum_{0 \le x < \frac{an+b} c} [n-\lfloor \frac{xc-b-c+1}a \rfloor]\\ =\lceil \frac {an+b} {c} \rceil n-f(c,1-b-c,a,\lceil \frac {an+b} {c}\rceil-1) \]

(因为 \(i\)\(0\) 开始,所以要用小于号)

这样每递归两次,\((a,c)\) 就变成 \((c, a\bmod c)\),因此时间复杂度为 \(O(\log (a+c))\).

由于 \(a < c, b < c\),所以 \(n\) 的值不会增大,无需担心爆 long long.