引入
Floor Sum
令 \(f(a,b,c,n)=\displaystyle \sum_{i=0}^{n}\lfloor\dfrac{a\times i+b}{c}\rfloor\)。我们要求的就是这个东西。
考虑如果 \(a,b\) 中有一个比 \(c\) 大。那么有：
\[f(a,b,c,n)=\sum_{i=0}^{n}\lfloor\dfrac{ai+b}{c}\rfloor
\]
\[=\sum_{i=0}^{n}\lfloor\dfrac{(\lfloor\dfrac{a}{c}\rfloor c+a\bmod c)i+(\lfloor\dfrac{b}{c}\rfloor c+b\bmod c)}{c}\rfloor
\]
\[=\sum_{i=0}^{n}\lfloor\dfrac{a}{c}\rfloor i+\lfloor\dfrac{b}{c}\rfloor+\lfloor\dfrac{(a\bmod c)i+b\bmod c}{c}\rfloor
\]
\[=\dfrac{n(n+1)}{2}\lfloor\dfrac{a}{c}\rfloor+(n+1)\lfloor\dfrac{b}{c}\rfloor+f(a\bmod c,b\bmod c,c,n)
\]
否则，我们考虑令 \(m=\lfloor\dfrac{an+b}{c}\rfloor\)。
\[\sum_{i=0}^{n}\lfloor\dfrac{ai+b}{c}\rfloor=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[j<\lfloor\dfrac{ai+b}{c}\rfloor]
\]
然后开始进行严肃等价变形。
\[j<\lfloor\dfrac{ai+b}{c}\rfloor=\lceil\dfrac{ai+b+1}{c}\rceil-1\iff j+1<\lceil\dfrac{ai+b+1}{c}\rceil
\]
\[\iff j+1<\dfrac{ai+b+1}{c}\iff \dfrac{cj+c-b-1}{a}<i\iff \lfloor\dfrac{cj+c-b-1}{a}\rfloor<i
\]
于是我们可以推出：
\[f(a,b,c,n)=\sum_{j=0}^{m-1}\sum_{i=0}^{n}[i>\lfloor\dfrac{cj+c-b-1}{a}\rfloor]
\]
\[=\sum_{j=0}^{m-1}(n-\lfloor\dfrac{cj+c-b-1}{a}\rfloor)=nm-f(c,c-b-1,a,m-1)
\]
然后就只需要用这两个东西来回倒腾就行了，复杂度大约是 \(\log\) 量级的。
代码