贡献：OI Wiki
这个算法确实挺妙的，所以我就写个笔记。
定义
这个算法需要用到一个函数：
$$ f(a,b,c,n)=\sum\limits_{i=0}^n \left\lfloor \dfrac{\color{red}a\color{default}i+\color{blue}b\color{default}}{\color{green}c\color{default}} \right\rfloor $$
在下面参数 $a$、$b$、$c$ 都会用三种颜色标出，以便于区分。
因为 $a$、$b$、$c$、$n$ 都很大，所以我们没法直接暴力求。
数论分块显然也不彳亍。
所以我们只能另辟蹊径了。
求值
咱从简单到复杂走。
1
首先，我们可以知道：
$$ \begin{aligned} f(a,b,c,n)&=\sum\limits_{i=0}^n \left\lfloor \dfrac{\color{red}a\color{default}i+\color{blue}b\color{default}}{\color{green}c\color{default}} \right\rfloor \ &=\sum\limits_{i=0}^n \left\lfloor \dfrac{(\lfloor \frac{a}{c} \rfloor c + a \bmod c)i+(\lfloor \frac{b}{c} \rfloor c + b \bmod c)}{c} \right\rfloor \ &=\sum\limits_{i=0}^n \left\lfloor \dfrac{\lfloor \frac{a}{c} \rfloor c \cdot i + a \bmod c \cdot i+\lfloor \frac{b}{c} \rfloor c + b \bmod c}{c} \right\rfloor \ &=\sum\limits_{i=0}^n \left( \left\lfloor \frac{a}{c} \right\rfloor i + \left\lfloor \frac{b}{c} \right\rfloor + \left\lfloor \dfrac{a \bmod c \cdot i+b \bmod c}{c} \right\rfloor \right) \ &=\dfrac{n(n+1)}{2} \left\lfloor \frac{a}{c} \right\rfloor + (n+1) \left\lfloor \frac{b}{c} \right\rfloor + \sum\limits_{i=0}^n \left\lfloor \dfrac{\color{red}a \bmod c\color{default} \cdot i+\color{blue}b \bmod c\color{default}}{\color{green}c\color{default}} \right\rfloor \ &=\dfrac{n(n+1)}{2} \left\lfloor \frac{a}{c} \right\rfloor + (n+1) \left\lfloor \frac{b}{c} \right\rfloor + f(a \bmod c,b \bmod c,c,n) \ \end{aligned} $$
所以经过一番推导，我们就可以把 $f(a,b,c,n)$ 转换到 $a,b<c$ 的形式。
2
但光是这样也不彳亍，我们并不知道这种形式如何处理，所以我们继续推导。
考虑贡献转换：（公式看不清的话可以放大）
$$ \begin{aligned} f(a,b,c,n)&=\sum\limits_{i=0}^n \left\lfloor \dfrac{\color{red}a\color{default}i+\color{blue}b\color{default}}{\color{green}c\color{default}} \right\rfloor \ &=\sum\limits_{i=0}^n \sum\limits_{j=0}^{\left\lfloor \frac{ai+b}{c} \right\rfloor-1} 1 \ &=\sum\limits_{j=0}^{\left\lfloor \frac{an+b}{c} \right\rfloor-1} \sum\limits_{i=0}^n \left[ ~ j<\left\lfloor \frac{ai+b}{c} \right\rfloor ~ \right] \ \end{aligned} $$
此时我们考虑把向下取整符号去掉：（$j \in \mathbb{Z}$）
$$ j<\lfloor x \rfloor \iff j+1 \leq \lfloor x \rfloor \iff j+1 \leq x $$
然后继续：（灰色是上面已有部分）
$$ \begin{aligned} f(a,b,c,n)&\color{gray}=\sum\limits_{i=0}^n \left\lfloor \dfrac{ai+b}{c} \right\rfloor \ &\color{gray}=\sum\limits_{i=0}^n \sum\limits_{j=0}^{\left\lfloor \frac{ai+b}{c} \right\rfloor-1} 1 \ &\color{gray}=\sum\limits_{j=0}^{\left\lfloor \frac{an+b}{c} \right\rfloor-1} \sum\limits_{i=0}^n \left[ ~ j<\left\lfloor \frac{ai+b}{c} \right\rfloor ~ \right] \ &=\sum\limits_{j=0}^{\left\lfloor \frac{an+b}{c} \right\rfloor-1} \sum\limits_{i=0}^n \left[ ~ j+1 \leq \frac{ai+b}{c} ~ \right] \ &=\sum\limits_{j=0}^{\left\lfloor \frac{an+b}{c} \right\rfloor-1} \sum\limits_{i=0}^n \left[ ~ jc+c \leq ai+b ~ \right] \ &=\sum\limits_{j=0}^{\left\lfloor \frac{an+b}{c} \right\rfloor-1} \sum\limits_{i=0}^n \left[ ~ jc+c-b \leq ai ~ \right] \ &=\sum\limits_{j=0}^{\left\lfloor \frac{an+b}{c} \right\rfloor-1} \sum\limits_{i=0}^n \left[ ~ jc+c-b-1<ai ~ \right] \ &=\sum\limits_{j=0}^{\left\lfloor \frac{an+b}{c} \right\rfloor-1} \sum\limits_{i=0}^n \left[ ~ \left\lfloor \dfrac{jc+c-b-1}{a} \right\rfloor <i ~ \right] \ \end{aligned} $$
这下向下取整里面的东西和 $i$ 没关系了，消了。
我们设 $m=\left\lfloor \frac{an+b}{c} \right\rfloor$，继续：（灰色是上面已有部分）
$$ \begin{aligned} f(a,b,c,n)&\color{gray}=\sum\limits_{i=0}^n \left\lfloor \dfrac{ai+b}{c} \right\rfloor \ &\color{gray}=\sum\limits_{i=0}^n \sum\limits_{j=0}^{\left\lfloor \frac{ai+b}{c} \right\rfloor-1} 1 \ &\color{gray}=\sum\limits_{j=0}^{m-1} \sum\limits_{i=0}^n \left[ ~ j<\left\lfloor \frac{ai+b}{c} \right\rfloor ~ \right] \ &\color{gray}=\sum\limits_{j=0}^{m-1} \sum\limits_{i=0}^n \left[ ~ j+1 \leq \frac{ai+b}{c} ~ \right] \ &\color{gray}=\sum\limits_{j=0}^{m-1} \sum\limits_{i=0}^n \left[ ~ jc+c \leq ai+b ~ \right] \ &\color{gray}=\sum\limits_{j=0}^{m-1} \sum\limits_{i=0}^n \left[ ~ jc+c-b \leq ai ~ \right] \ &\color{gray}=\sum\limits_{j=0}^{m-1} \sum\limits_{i=0}^n \left[ ~ jc+c-b-1<ai ~ \right] \ &\color{gray}=\sum\limits_{j=0}^{m-1} \sum\limits_{i=0}^n \left[ ~ \left\lfloor \dfrac{jc+c-b-1}{a} \right\rfloor <i ~ \right] \ &=\sum\limits_{j=0}^{m-1} \left( n-\left\lfloor \dfrac{jc+c-b-1}{a} \right\rfloor \right) \ &=nm-\sum\limits_{j=0}^{m-1} \left\lfloor \dfrac{j\color{red}c\color{default}+\color{blue}c-b-1\color{default}}{\color{green}a\color{default}} \right\rfloor \ &=nm-f(c,c-b-1,a,m-1) \ \end{aligned} $$
所以我们就可以通过一车操作把 $a$ 和 $c$ 交换。
接下来我们继续像上面一样让 $a$ 模 $c$，以此往复，就像欧几里得算法一样。
所以最终复杂度就是 $O(\log)$ 级别的。
总结
式子：
$$ f(a,b,c,n)=\dfrac{n(n+1)}{2} \left\lfloor \frac{a}{c} \right\rfloor + (n+1) \left\lfloor \frac{b}{c} \right\rfloor + f(a \bmod c,b \bmod c,c,n) $$
设 $m=\left\lfloor \frac{an+b}{c} \right\rfloor$：
$$ f(a,b,c,n)=nm-f(c,c-b-1,a,m-1) $$
递归即可。