定义
这个算法用于求一条直线下整点个数，我们定义
[F(a, b, c, n) = sum_{i = 0}^{n} lfloor frac{ai + b}{c}
floor
]
其他几个乘系数的扩展不想学了TAT
推导
(a ge c) 或 (b ge c)
当 (a ge c) 或 (b ge c) 时，我们考虑把分子对 (c) 的商和余数分别提出来，那么有
[egin{aligned}
F(a, b, c, n)
&= sum_{i = 0}^{n} ((lfloor frac{(a mod c)i + (b mod c)}{c}
floor) i + lfloor frac ac
floor i + lfloor frac bc
floor)\
&= F(a mod c, b mod c, c, n) + frac{n(n + 1)}{2} lfloor frac ac
floor + (n + 1) lfloor frac bc
floor
end{aligned}
]
(a < c) 且 (b < c)
当 (a < c) 且 (b < c) 时，用几何意义转化为一条直线与 (x) 轴 (y) 轴以及 (x = n) 围成直角梯形内的整点个数。
设上界 (displaystyle m = lfloor frac{an + b}{c} floor) ，那么我们考虑拆式子
[egin{aligned}
F(a, b, c, n)
&= sum_{i = 0}^n sum_{j = 1}^m [lfloor frac{ai + b}{c}
floor ge j] \
&= sum_{i = 0}^n sum_{j = 0}^{m - 1} [lfloor frac{ai + b}{c}
floor ge j + 1] \
&= sum_{i = 0}^n sum_{j = 0}^{m - 1} [(frac{ai + b}{c}) ge j + 1]\
&= sum_{i = 0}^n sum_{j = 0}^{m - 1} [ai ge jc + c - b]\
&= sum_{i = 0}^n sum_{j = 0}^{m - 1} [i ge frac{jc + c - b}{a}]\
end{aligned}
]
很多地方都可以舍掉取整，因为整数和分数比较大小（考虑等于）的时候可以忽略下取整。
考虑分子减 (1) 换成 (>) 并交换和式：
[egin{aligned}
F(a, b, c, n)
&= sum_{i = 0}^n sum_{j = 0}^{m - 1} [i > frac{jc + c - b - 1}{a}]\
&= sum_{j = 0}^{m - 1} sum_{i = 0}^n [i > frac{jc + c - b - 1}{a}]\
&= sum_{j = 0}^{m - 1} (n - frac{jc + c - b - 1}{a})\
&= nm - sum_{j = 0}^{m - 1} frac{jc + c - b - 1}{a}\
&= nm - F(c, c - b - 1, a, m - 1)
end{aligned}
]
然后我们就可以递归处理了。
复杂度证明
我们只观察 (ac) 两位，如果 (a > c) 那么 (a mod c) ，否则交换 (ac) 。
那么复杂度其实和扩展欧几里得算法是一样的 (mathcal O(log n)) 。
代码
求 (f) 还是比较短的。
ll f(ll a, ll b, ll c, ll n) {
if (!a) return b / c * (n + 1);
if (a >= c || b >= c)
return f(a % c, b % c, c, n) + (a / c) * n * (n + 1) / 2 + (b / c) * (n + 1);
ll m = (a * n + b) / c;
return n * m - f(c, c - b - 1, a, m - 1);
}