• 求 $F(a,b,c,n)=\sum\limits_{i=0}^{n} \lfloor \frac{ai+b}{c} \rfloor$
• 求 $G(a,b,c,n)=\sum\limits_{i=0}^{n} \lfloor \frac{ai+b}{c} \rfloor^2$
• 求 $H(a,b,c,n)=\sum\limits_{i=0}^{n}i\lfloor \frac{ai+b}{c} \rfloor$

第一问

$(a \ge c )\vee(b \ge c)$

$$\begin{aligned} &F(a, b, c, n) \\ =&\sum_{i = 0}^{n}\left\lfloor\frac{a i+b}{c}\right\rfloor \\ =&\sum_{i = 0}^{n}\left(\left\lfloor\frac{\left.\left\lfloor\frac{a}{c}\right\rfloor c+(a \bmod c)\right) i+\left(\left\lfloor\frac{b}{c}\right\rfloor c+(b \bmod c)\right)}{c}\right\rfloor\right) \\ =&\sum_{i = 0}^{n}\left(\left\lfloor\frac{(a \bmod c) i+(b \bmod c)}{c}\right\rfloor+i\left\lfloor\frac{a}{c}\right\rfloor+\left\lfloor\frac{b}{c}\right\rfloor\right) \\ =&\sum_{i = 0}^{n}\left\lfloor\frac{(a \bmod c) i+(b \bmod c)}{c}\right\rfloor+\sum_{i = 0}^{n} i\left\lfloor\frac{a}{c}\right\rfloor+\sum_{i = 0}^{n}\left\lfloor\frac{b}{c}\right\rfloor \\ =&F(a \bmod c, b \bmod c, c, n)+\frac{n(n+1)}{2}\left\lfloor\frac{a}{c}\right\rfloor+(n+1)\left\lfloor\frac{b}{c}\right\rfloor \end{aligned}$$

$(a<c) \wedge (b<c)$

• $n=\sum\limits_{i=0}^{n-1}1$
• $[x]$ 被称为“艾弗森括号”，当 $x$ 为真时它为 $1$，否则为 $0$。根据定义有 $\sum\limits_{i=0}^{n}[i>x]=n-x$

$$\begin{aligned} &j<\left \lfloor \frac{ai+b}{c} \right\rfloor\\ \Rightarrow &j+1 \le \left \lfloor \frac{ai+b}{c} \right \rfloor\\ \Rightarrow &j+1 \le \frac{ai+b}{c}\\ \Rightarrow &j+c+c-b \le ai\\ \Rightarrow &jc+c-b-1 < ai\\ \Rightarrow &i>\left \lfloor \frac{jc+c-b-1}{a}\right \rfloor \end{aligned}$$ $$\begin{aligned} &F(a,b,c,n)\\ =&\sum_{i=0}^{m-1}\left(n-\left\lfloor \frac{ci+(c-b-1)}{a} \right\rfloor\right) \\ =&\sum_{i=0}^{m-1}n-\sum_{i=0}^{m-1}\left\lfloor \frac{ci+(c-b-1)}{a} \right\rfloor\\ =&nm-F(c,c-b-1,a,m-1) \end{aligned}$$

边界情况

$$\begin{aligned} &F(0,b,c,n)\\ =&\sum_{i=0}^{n} \lfloor \frac{b}{c} \rfloor\\ =&(n+1)\lfloor \frac{b}{c} \rfloor \end{aligned}$$

总结

$$F(a, b, c, n)= \left\{\begin{array}{c} (n+1)\left\lfloor\frac{b}{c}\right\rfloor & a=0 \\ \left\lfloor\frac{b}{c}\right\rfloor&n=0 \\ F(a \bmod c, b \bmod c, c, n)+\frac{n(n+1)}{2}\left\lfloor\frac{a}{c}\right\rfloor+(n+1)\left\lfloor\frac{b}{c}\right\rfloor&(a \geq c) \vee (b \geq c)\\ n m-F(c, c-b-1, a, m-1) &(a<c) \wedge (b<c) \end{array}\right.$$

第二问

$(a \ge c )\vee(b \ge c)$

$$\begin{aligned} &G(a,b,c,n)\\ =&\sum^{n}_{i=0}\left \lfloor \frac{ai+b}{c}\right \rfloor ^2\\ =&\sum^n_{i=0}\left \lfloor \frac{\left (\left \lfloor \frac{a}{c}\right \rfloor c +(a\bmod c) \right )i+\left \lfloor \frac{b}{c}\right \rfloor c+(b \bmod c)}{c} \right \rfloor ^2\\ =&\sum^n_{i=0}\left \lfloor \left \lfloor \frac{a}{c} \right \rfloor i+\left \lfloor \frac{b}{c} \right \rfloor +\frac{(a \bmod c)i+(b \bmod c)}{c} \right \rfloor ^2 \end{aligned}$$ $$\begin{aligned} &\sum_{i=0}^{n}\left(\left\lfloor\frac{a}{c}\right\rfloor^{2} i^{2}+\left\lfloor\frac{b}{c}\right\rfloor^{2}+t^{2}+2\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor i+2\left\lfloor\frac{a}{c}\right\rfloor i t+2\left\lfloor\frac{b}{c}\right\rfloor t\right) \\ =&\sum_{i=0}^{n}\left\lfloor\frac{a}{c}\right\rfloor^{2} i^{2}+\sum_{i=0}^{n}\left\lfloor\frac{b}{c}\right\rfloor^{2}+\sum_{i=0}^{n} t^{2}+\sum_{i=0}^{n} 2\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor i+\sum_{i=0}^{n} 2\left\lfloor\frac{a}{c}\right\rfloor i t+\sum_{i=0}^{n} 2\left\lfloor\frac{b}{c}\right\rfloor t \\ \end{aligned}$$ $$\begin{aligned} G(a, b, c, n)&=G(a \bmod c, b \bmod c, c, n)+2\left\lfloor\frac{a}{c}\right\rfloor H(a \bmod c, b \bmod c, c, n)+2\left\lfloor\frac{b}{c}\right\rfloor F(a \bmod c, b \bmod c, c, n) \\ &+(n+1)\left\lfloor\frac{b}{c}\right\rfloor^{2}+\left\lfloor\frac{a}{c}\right\rfloor^{2} \frac{n(n+1)(2 n+1)}{6}+\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor n(n+1) \\ \end{aligned}$$

$(a<c) \wedge(b<c)$

$$\begin{aligned} &n^2\\ =&(n^2+n)-n\\ =&2\times\frac{n(n+1)}{2}-n\\ =&\left(2\sum^{n}_{i=1} i\right )-n \end{aligned}$$ $$\begin{aligned} &G(a, b, c, n)\\ =&\sum_{i=0}^{n}\left(2 \sum_{j=1}^{\left\lfloor\frac{a i+b}{c}\right\rfloor} j-\left\lfloor\frac{a i+b}{c}\right\rfloor\right) \\ =&2 \sum_{i=0}^{n} \sum_{j=0}^{\left\lfloor \frac{a i+b}{c}\right\rfloor -1}(j+1)-F(a, b, c, n) \\ \end{aligned}$$ $$2 \sum_{j=0}^{m-1}(j+1) \sum_{i=0}^{n}\left[j<\left\lfloor\frac{a i+b}{c}\right\rfloor\right] \\$$ $$\begin{aligned} &2 \sum_{j=0}^{m-1}(j+1) \sum_{i=0}^{n}\left[i>\left\lfloor\frac{j c+c-b-1}{a}\right\rfloor\right] \\ =&2 \sum_{j=0}^{m-1}(j+1)\left(n-\left\lfloor\frac{j c+c-b-1}{a}\right\rfloor\right) \\ =&2 \sum_{i=0}^{m-1}\left(n i+n-i\left\lfloor\frac{c i+c-b-1}{a}\right\rfloor-\left\lfloor\frac{c i-c-b-1}{a}\right\rfloor\right) \\ =&n m(m+1)-2 H(c, c-b-1, a, m-1)-2 F(c, c-b-1, a, m-1) \\ \end{aligned}$$

边界情况

总结

$$G(a, b, c, n) =\left\{\begin{array}{c} (n+1)\left\lfloor\frac{b}{c}\right\rfloor^{2} &a=0 \\ \left\lfloor\frac{b}{c}\right\rfloor^{2} &n=0 \\ n m(m+1)-2 H(c, c-b-1, a, m-1)-2 F(c, c-b-1, a, m-1)-F(a, b, c, n) &a<c \wedge b<c \\ G(a \bmod c, b \bmod c, c, n)+2\left\lfloor\frac{a}{c}\right\rfloor H(a \bmod c, b \bmod c, c, n)+2\left\lfloor\frac{b}{c}\right\rfloor F(a \bmod c, b \bmod c, c, n)+\\ (n+1)\left\lfloor\frac{b}{c}\right\rfloor^{2}+\left\lfloor\frac{a}{c}\right\rfloor^{2} \frac{n(n+1)(2 n+1)}{6}+\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor n(n+1) &a \geq c \vee b \geq c\\ \end{array}\right.$$

第三问

$(a \ge c )\vee(b \ge c)$

$$\begin{aligned} &H(a, b, c, n)=\sum_{i=0}^{n} i\left|\frac{a i+b}{c}\right| \\ =&\sum_{i=0}^{n} i\left[\frac{\left(a \bmod c+\left\lfloor\frac{a}{c}\right\rfloor c\right) i+\left(b \bmod c+\left\lfloor\frac{b}{c}\right\rfloor c\right)}{c}\right] \\ =&\sum_{i=0}^{n} i\left|\frac{(a \bmod c) i+(b \bmod c)}{c}+i\right| \frac{a}{c}\left|+\left|\frac{b}{c}\right|\right| \\ =&\sum_{i=0}^{n} i\left|\frac{(a \bmod c) i+(b \bmod c)}{c}\right|+\sum_{i=0}^{n} i^{2}\left\lfloor\frac{a}{c}\right\rfloor+\sum_{i=0}^{n} i\left|\frac{b}{c}\right| \\ =&H(a \bmod c, b \bmod c, c, n)+\frac{n(n+1)(2 n+1)}{6}\left\lfloor\frac{a}{c}\right\rfloor+\frac{n(n+1)}{2}\left\lfloor\frac{b}{c}\right\rfloor \\ \end{aligned}$$

$(a<c) \wedge(b<c)$

$$\begin{aligned} &H(a,b,c,n)\\ =&\sum_{i=0}^{n} i\left|\frac{a i+b}{c}\right| \\ =&\sum_{i=0}^{n} i \sum_{j=0}^{\left\lfloor\left.\frac{ai+b}{c}\right|-1\right.} 1 \\ =&\sum_{j=0}^{m-1} \sum_{i=0}^{n}i\left[ j<\left \lfloor \frac{ai+b}{c} \right \rfloor \right]\\ =&\sum_{j=0}^{m-1} \sum_{i=0}^{n} i\left[i>\left[\frac{j c+(c-b-1)}{a}\right]\right] \\ \end{aligned}$$ $$\begin{aligned} &H(a, b, c, n)\\ =&\sum_{j=0}^{m-1} \sum_{i=0}^{n} i[i>t] \\ =&\sum_{j=0}^{m-1} \sum_{i=t+1}^{n} i \\ =&\sum_{j=0}^{m-1} \frac{(n-t)(n+t+1)}{2} \\ =&\frac{1}{2} \sum_{j=0}^{m-1}\left(n(n+1)-t^{2}-t\right) \\ =&\frac{1}{2}\left(m n(n+1)-\sum_{i=0}^{m-1} t^{2}-\sum_{i=0}^{m-1} t\right) \\ \end{aligned}$$ $$\begin{aligned} &\frac{1}{2}\left(m n(n+1)-\sum_{i=0}^{m-1}\left\lfloor\left.\frac{c i+c-b-1}{a}\right|^{2}-\sum_{i=0}^{m-1}\left\lfloor\frac{c i+c-b-1}{a}\right\rfloor\right)\right. \\ =&\frac{1}{2}(mn(n+1)-G(c, c-b-1, a, m-1)-F(c, c-b-1, a, m-1)) \\ \end{aligned}$$

边界情况

总结

$$\begin{aligned} H(a, b, c, n) =\left\{\begin{array}{c} 0 &n=0 \\ \frac{n(n+1)}{2}\left\lfloor\frac{b}{c}\right\rfloor&a=0 \\ H(a \bmod c, b \bmod c, c, n)+\frac{n(n+1)(2 n+1)}{6}\left\lfloor\frac{a}{c}\right\rfloor +\frac{n(n+1)}{2}\left\lfloor \frac{b}{c}\right\rfloor & (a \geq c) \vee (b \geq c) \\ \frac{1}{2}(m n(n+1)-G(c, c-b-1,a, m-1)-F(c, c-b-1, a, m-1))& (a<c) \wedge (b<c) \end{array}\right. \end{aligned}$$

代码