皮克定理连续自然数的平方和的求和公式常见除法同余式

涉及知识点

皮克定理.
平方和求和公式。 $\frac{A}{b} \bmod c=\frac{a \bmod (bc)}{b}$ .　　

分析

显然，x,y,z都正整数，并且只需要符合 $x+y+z\leq k$ 即可。我们固定一个z，将其变成 $x+y<=k-z=a$ .这就变成了平面上求平面区域内部及边界上点的个数的问题，运用皮克定理 $S=n+\frac{s}{2}-1$ .两边同时加上 $\frac{s}{2}$ 就容易得到 $ans(a)=S+\frac{s}{2}+1=\frac{3a}{2}+\frac{a^2}{2}+1$ ,总的答案就是 $ans=\sum\limits_{a=0}^{k}ans(a)$ .这个就要用到等差数列求和公式和平方和求和公式，最后推到式子是 $ans=(k)(k+1)(k+5)/6+(k+1)=(k)(k+1)/2*(k+5)/3+(k+1)$ .
注意会爆long long，需要用 $\frac{A}{b} \bmod c=\frac{a \bmod (bc)}{b}$ 这个公式对 $(k)(k+1)/2$ 的中间结果先模 $3m$ ,一开始我想当然模 $m$ ，自然gg了。

皮克定理 连续自然数的平方和的求和公式 常见除法同余式

涉及知识点

分析

皮克定理连续自然数的平方和的求和公式常见除法同余式