快速求\(1^2 + 2^2 + 3^2 + \dotsb + n^2\)模11的余数
我们来证明一下\(1^2 + 2^2 + 3^2 + \dotsb + n^2\)的通项公式是\(\frac{n(n+1)(2n+1)}{6}\), 然后就可以\(O(1)\)直接算这个式子:
Lemma 1: 对于任意的\(n \geqslant 2\) 恒有 \(\tbinom{2}{2} + \tbinom{3}{2} + \tbinom{4}{2} + \dotsb + \tbinom{n}{2} = \tbinom{n + 1}{3}\)
Proof:
当\(n = 2\)时显然成立,
假设当\(n = k\)时也成立, 当\(n = k + 1\)时,
\[LHS = \tbinom{2}{2} + \dotsb + \tbinom{k}{2} + \tbinom{k+1}{2} =
\tbinom{k + 1}{3} + \tbinom{k + 1}{2} = \tbinom{k + 2}{3}\]
(由帕斯卡恒等式得来), 证毕
Proof2:
由Lemma 1中式子, 直接展开, 有
\[LHS = \frac{2^2-2}{2} + \frac{3^2-3}{2} + \dotsb + \frac{n^2 - n}{2} =
\frac{(n+1)(n-1)n}{6} = RHS\]
式子变换就有,
\[\frac{1}{2} (2^2 + 3^2 + \dotsb + n^2) = \frac{(n+1)(n-1)n}{6} +
\frac{1}{2}(2 + 3 + \dotsb + n)\]
代数运算, 即可得到最终公式