复述题解：
我们记 \(f(a,b,c,n)=\sum\limits_{i=0}^{n}\Big\lfloor \dfrac{ai+b}{c} \Big\rfloor\,,\ g(a,b,c,n)=\sum\limits_{i=0}^{n}i\Big\lfloor \dfrac{ai+b}{c} \Big\rfloor\,,\ h(a,b,c,n)=\sum\limits_{i=0}^{n}{\Big\lfloor \dfrac{ai+b}{c} \Big\rfloor}^2\)
第零部分·概况
基本上就是先把 \(a\) 和 \(b\) 对 \(c\) 取模，看看对答案的贡献，然后再推推式子，推出来可以递归求解的一个过程。
我们令两个神秘数字：
\[m=\bigg\lfloor\frac{an+b}{c} \bigg\rfloor\,,\,t=\bigg\lfloor\frac{jc+c+b-1}{a}\bigg\rfloor \]第一部分·求解 \(f\)
取模部分
\[\begin{aligned} f(a,b,c,n)&=\sum\limits_{i=0}^{n}\bigg\lfloor \frac{ai+b}{c} \bigg\rfloor =\sum\limits_{i=0}^{n}\bigg\lfloor \frac{(\lfloor \frac{a}{c} \rfloor \cdot c + a\bmod c)i+(\lfloor \frac{b}{c} \rfloor \cdot c + b\bmod c)}{c} \bigg\rfloor \\ &=\sum\limits_{i=0}^{n}\bigg\lfloor \lfloor \frac{a}{c} \rfloor i+\lfloor \frac{b}{c} \rfloor+\frac{(a\bmod c)i+(b\bmod c)}{c} \bigg\rfloor \\&= \sum\limits_{i=0}^{n} (\bigg\lfloor \frac{a}{c} \bigg\rfloor i+\bigg\lfloor \frac{b}{c} \bigg\rfloor+\bigg\lfloor \frac{(a\bmod c)i+(b\bmod c)}{c} \bigg\rfloor) \\&= \bigg\lfloor \frac{a}{c} \bigg\rfloor \big(\sum\limits_{i=0}^{n}i\big)+ \bigg\lfloor \frac{b}{c} \bigg\rfloor\big(\sum\limits_{i=0}^{n}1\big) + f(a\bmod c,b\bmod c,c,n) \\&= \frac{n(n+1)}{2} \bigg\lfloor \frac{a}{c} \bigg\rfloor+ (n+1)\bigg\lfloor \frac{b}{c} \bigg\rfloor + f(a\bmod c,b\bmod c,c,n)\end{aligned}\]推式子部分
\[f(a,b,c,n)=\sum\limits_{i=0}^{n}\bigg\lfloor \frac{ai+b}{c} \bigg\rfloor = \sum\limits_{i=0}^{n}\sum\limits_{j=0}^{\lfloor \frac{ai+b}{c} \rfloor-1}1 = \sum\limits_{j=0}^{\lfloor \frac{an+b}{c} \rfloor-1}\sum\limits_{i=0}^{n}[j<\lfloor\frac{ai+b}{c}\rfloor] \]\[\begin{aligned} \because j<\lfloor\frac{ai+b}{c}\rfloor &\Leftrightarrow j+1\le\lfloor\frac{ai+b}{c}\rfloor \Leftrightarrow j+1\le \frac{ai+b}{c} \\ &\Leftrightarrow jc+c\le ai+b \Leftrightarrow jc+c+b\le ai \\ &\Leftrightarrow jc+c+b-1 <ai \Leftrightarrow \frac{jc+c+b-1}{a}<i \\ &\Leftrightarrow \lfloor\frac{jc+c+b-1}{a}\rfloor<i \Leftrightarrow t<i \end{aligned} \]\[\begin{aligned} \therefore f(a,b,c,n)&=\sum\limits_{j=0}^{m-1}\sum\limits_{i=0}^{n}[t<i]=\sum\limits_{j=0}^{m-1}(n-t) \\&=nm- \sum\limits_{j=0}^{m-1 }\lfloor\frac{jc+c+b-1}{a}\rfloor \\&=nm - f(c,c+b-1,a,m-1) \end{aligned} \]第二部分·求解 \(g\)
取模部分
\[\begin{aligned} g(a,b,c,n)&=\sum\limits_{i=0}^{n}i\lfloor \frac{ai+b}{c} \rfloor =\sum\limits_{i=0}^{n}i\bigg\lfloor \frac{(\lfloor \frac{a}{c} \rfloor \cdot c + a\bmod c)i+(\lfloor \frac{b}{c} \rfloor \cdot c + b\bmod c)}{c} \bigg\rfloor \\&= \sum\limits_{i=0}^{n} i(\bigg\lfloor \frac{a}{c} \bigg\rfloor i+\bigg\lfloor \frac{b}{c} \bigg\rfloor+\bigg\lfloor \frac{(a\bmod c)i+(b\bmod c)}{c} \bigg\rfloor) \\&= \bigg\lfloor \frac{a}{c} \bigg\rfloor \big(\sum\limits_{i=0}^{n}i^2\big)+ \bigg\lfloor \frac{b}{c} \bigg\rfloor\big(\sum\limits_{i=0}^{n}i\big) + g(a\bmod c,b\bmod c,c,n) \\&= \frac{n(n+1)(2n+1)}{6}\bigg\lfloor \frac{a}{c} \bigg\rfloor + \frac{n(n+1)}{2}\bigg\lfloor \frac{b}{c} \bigg\rfloor\ + g(a\bmod c,b\bmod c,c,n) \end{aligned}\]推式子部分
\[\begin{aligned} g(a,b,c,n)&=\sum\limits_{i=0}^{n}i\bigg\lfloor \frac{ai+b}{c} \bigg\rfloor = \sum\limits_{i=0}^{n}\sum\limits_{j=0}^{\lfloor \frac{ai+b}{c} \rfloor-1}i = \sum\limits_{j=0}^{\lfloor \frac{an+b}{c} \rfloor-1}\sum\limits_{i=0}^{n}[j<\lfloor\frac{ai+b}{c}\rfloor]i \\&=\sum\limits_{j=0}^{m-1}\sum\limits_{i=0}^{n}[t<i]i =\sum\limits_{j=0}^{m-1}\sum\limits_{i=t+1}^{n}i=\sum\limits_{j=0}^{m-1}\frac{(t+1+n)(n-t)}{2} \\&=\frac{1}{2}\sum\limits_{j=0}^{m-1}\Big(nt+n+n^2-t^2-t-nt\Big) \\&=\frac{1}{2}\sum\limits_{j=0}^{m-1}\Big(n^2+n-t^2-t\Big) \\&=\frac{1}{2}\Big(nm(n+1)-\sum\limits_{j=0}^{m-1}t^2-\sum\limits_{j=0}^{m-1}t\Big) \\&=\frac{1}{2}\Big(nm(n+1)-h(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\Big) \end{aligned}\]第三部分·求解 \(h\)
取模部分
\[\begin{aligned} h(a,b,c,n) =&\sum\limits_{i=0}^{n}\lfloor \frac{ai+b}{c} \rfloor^2 =\sum\limits_{i=0}^{n}\bigg\lfloor \frac{(\lfloor \frac{a}{c} \rfloor \cdot c + a\bmod c)i+(\lfloor \frac{b}{c} \rfloor \cdot c + b\bmod c)}{c} \bigg\rfloor^2 \\=& \sum\limits_{i=0}^{n} (\bigg\lfloor \frac{a}{c} \bigg\rfloor i+\bigg\lfloor \frac{b}{c} \bigg\rfloor+\bigg\lfloor \frac{(a\bmod c)i+(b\bmod c)}{c} \bigg\rfloor)^2 \\=& \sum\limits_{i=0}^{n} ( \bigg\lfloor \frac{a}{c}\bigg\rfloor^2i^2+ \bigg\lfloor \frac{b}{c} \bigg\rfloor^2+ \bigg\lfloor \frac{(a\bmod c)i+(b\bmod c)}{c} \bigg\rfloor^2 + 2\cdot\bigg\lfloor \frac{a}{c}\bigg\rfloor i \bigg\lfloor \frac{b}{c} \bigg\rfloor \\&+2\cdot\bigg\lfloor \frac{a}{c}\bigg\rfloor i \bigg\lfloor \frac{(a\bmod c)i+(b\bmod c)}{c} \bigg\rfloor+ 2\cdot \bigg\lfloor \frac{b}{c} \bigg\rfloor \bigg\lfloor \frac{(a\bmod c)i+(b\bmod c)}{c} \bigg\rfloor ) \\=&\bigg\lfloor \frac{a}{c}\bigg\rfloor^2\frac{n(n+1)(2n+1)}{6}+ \bigg\lfloor \frac{b}{c} \bigg\rfloor^2 (n+1)+h(a\bmod c,b\bmod c,c,n) +2\bigg\lfloor \frac{a}{c}\bigg\rfloor\bigg\lfloor \frac{b}{c} \bigg\rfloor \frac{n(n+1)}{2} \\& + 2\bigg\lfloor \frac{a}{c}\bigg\rfloor \sum\limits_{i=0}^{n}i\bigg\lfloor \frac{(a\bmod c)i+(b\bmod c)}{c} \bigg\rfloor + 2\bigg\lfloor \frac{b}{c} \bigg\rfloor\sum\limits_{i=0}^{n}\bigg\lfloor \frac{(a\bmod c)i+(b\bmod c)}{c} \bigg\rfloor \\=&\bigg\lfloor \frac{a}{c}\bigg\rfloor^2\frac{n(n+1)(2n+1)}{6}+ \bigg\lfloor \frac{b}{c} \bigg\rfloor^2 (n+1)+h(a\bmod c,b\bmod c,c,n) +\bigg\lfloor \frac{a}{c}\bigg\rfloor\bigg\lfloor \frac{b}{c} \bigg\rfloor n(n+1) \\& + 2\bigg\lfloor \frac{a}{c}\bigg\rfloor g(a\bmod c,b\bmod c,c,n) + 2\bigg\lfloor \frac{b}{c} \bigg\rfloor f(a\bmod c,b\bmod c,c,n) \end{aligned}\]推式子部分
这里要用到一个神秘的东西：
\[n^2=2\cdot\frac{n(n+1)}{2}-n=(2\sum\limits_{i=0}^{n}i)-n \]\[\begin{aligned} g(a,b,c,n)=&\sum\limits_{i=0}^{n}\bigg\lfloor \frac{ai+b}{c} \bigg\rfloor^2 =\sum\limits_{i=0}^{n}\Big(2\sum\limits_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor}j-\Big\lfloor\frac{ai+b}{c}\Big\rfloor\Big) \\=&2\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor}j-\sum\limits_{i=0}^{n} \Big\lfloor\frac{ai+b}{c}\Big\rfloor \\=& 2\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor -1}(j+1)-f(a,b,c,n) \\=& 2\sum\limits_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}(j+1)\sum\limits_{i=0}^{n}[j<\Big\lfloor\frac{ai+b}{c}\Big\rfloor] -f(a,b,c,n) \\=& 2\sum\limits_{j=0}^{m-1}(j+1)\sum\limits_{i=0}^{n}[i>t] -f(a,b,c,n) \\=& 2\sum\limits_{j=0}^{m-1}(j+1)(n-t) -f(a,b,c,n) \\=& 2\sum\limits_{j=0}^{m-1}\Big(n(j+1)-tj-t\Big) -f(a,b,c,n) \\=& 2\Big(n\sum\limits_{j=0}^{m-1}(j+1) -\sum\limits_{j=0}^{m-1}tj-\sum\limits_{j=0}^{m-1}t\Big) -f(a,b,c,n) \\=& 2\Big(n\sum\limits_{j=1}^{m}j -g(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\Big) -f(a,b,c,n) \\=& 2 n\frac{m(m+1)}{2} -2g(c,c-b-1,a,m-1)-2f(c,c-b-1,a,m-1)-f(a,b,c,n) \\=& 2 nm(m+1) -2g(c,c-b-1,a,m-1)-2f(c,c-b-1,a,m-1)-f(a,b,c,n) \end{aligned}\]终于！！！我写完了这刘拓世！！！我真的自己也不想再看它一眼了……
我们发现这三个函数的计算过程都是在递归，而且传下去的内容也一样，于是我们把这三个的计算扔进一个函数里，一同计算。
这样这个模板题就做完了，提交记录
以上便是我此时此刻对这玩意的全部理解，只会模板题。
标签：lfloor,frac,limits,欧几里得,rfloor,算法,sum,bigg From： https://www.cnblogs.com/baoyangawa/p/17997360