P5174
aleph_blanc
·
2021-09-27 16:44:39
·
个人记录
一切开始之前，我们先推导一个引理：
\large{
\begin{aligned}
&f(n)=\sum_{i=0}^ni^2,n\ge0\\
&f(n)=\frac{n(n+1)(2n+1)}{6}
\end{aligned}
}
这里提供五种 推导它的方法。
一、查找法
通过搜索引擎，题解，文献等，我们找到了这个公式：
\large f(n)=\frac{n(n+1)(2n+1)}{6}
[doge]
二、归纳法
\large
\begin{aligned}
&f(n)=\frac{n(n+1)(2n+1)}{6}\\
&=\frac{n(n+1)(n+\frac{1}{2})}{3}\\
&\\
&f(0)=0\\
&f(n)=f(n-1)+n^2\\
&3f(n)=(n-1)n(n-\frac{1}{2})+3n^2\\
&=(n^3-\frac{3}{2}n+\frac{1}{2}n)+3n^2\\
&=n^3+\frac{3}{2}n^2+\frac{1}{2}n\\
&=n(n+\frac{1}{2})(n+1)\\
&\text{故对于所有的}n\ge0,f(n)=\frac{n(n+1)(2n+1)}{6}
\end{aligned}
三、二重合式展开与收缩
\large
\begin{aligned}
&f(n)=\sum_{k=1}^nk^2\\
&=\sum_{j=1}^n\sum_{k=j}^nk\\
&=\sum_{j=1}^n\frac{j+n}{2}(n-j+1)\\
&=\frac{1}{2}\sum_{j=1}^n(n(n+1)+j-j^2)\\
&=\frac{1}{2}n^2(n+1)+\frac{1}{4}n(n+1)-\frac{1}{2}f(n)\\
&=\frac{1}{2}n(n+\frac{1}{2})(n+1)-\frac{1}{2}f(n)\\
&\\
&\frac{3}{2}f(n)=\frac{1}{2}n(n+\frac{1}{2})(n+1)\\
&f(n)=\frac{n(n+1)(2n+1)}{6}
\end{aligned}
对 \sum_{k=1}^nk^2=\sum_{j=1}^n\sum_{k=j}^nk 的解释：
我们知道，一个数 n 加和 n 次，就是 n^2 。
将右式展开：
1+2+3+4+5+6+...+n
2+3+4+5+6+...+n
3+4+5+6+...+n
4+5+6+...+n
5+6+...+n
6+...+n
...
...+n刚好每个数 k 加 k 次，与原式等价。
四、瞎搞法
利用恒等式 \large(n+1)^3=n^3+3n^2+3n+1 ，可以得到：
\large
\begin{aligned}
&(n+1)^3-n^3=3n^2+3n+1\\
&n^3-(n-1)^3=3(n-1)^2+3(n-1)+1\\
&\cdots\cdots\\
&2^3-1^3=3*(1^2)+3*1+1
\end{aligned}
把这 \large n 个等式两端分别相加，得：
\large
\begin{aligned}
&(n+1)^3-1\\
&=3\times\frac{n(n+1)}{2}+n+3\sum_{i=1}^ni^2\\
&n^3+3n^2+3n\\
&=3\times\frac{n(n+1)}{2}+n+3\sum_{i=1}^ni^2\\
\end{aligned}
整理后得：
\large\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6}
五、扰动法
这是最实用的方法。
对于 f(n+1) ，抽出 (n+1)^2,0^2 。
\large
\begin{aligned}
&f(n)+(n+1)^2\\
&=\sum_{k=0}^n(k+1)^2\\
&=\sum_{k=0}^n(k^2+2k+1)\\
&=\sum_{k=0}^nk^2+2\sum_{k=0}^nk+\sum_{k=0}^n1\\
&=f(n)+2\sum_{k=0}^nk+(n+1)\\
&\\
&\sum_{k=0}^nk=\frac{1}{2}((n+1)^2-(n+1))=\frac{n(n+1)}{2}
\end{aligned}
额。。。有个毛用？
等等，二次幂可以推出一次幂求和，那是不是三次幂可以推出二次幂求和？
设
\large g(n)=\sum_{k=0}^nk^3
从 g(n) 中抽出 (n+1)^3, 0^3 。
\large
\begin{aligned}
&g(n)+(n+1)^3\\
&=\sum_{k=0}^n(k+1)^3\\
&=\sum_{k=0}^n(k^3+3k^2+3k+1)\\
&=\sum_{k=0}^nk^3+3\sum_{k=0}^nk^2+3\sum_{k=0}^nk+\sum_{k=0}^n1\\
&=g(n)+3f(n)+\frac{3n(n+1)}{2}+(n+1)\\
&\\
&3f(n)=(n+1)^3-\frac{3n(n+1)}{2}-(n+1)\\
&=n^3+3n^2+3n+1-\frac{3n^2+3n}{2}-n-1\\
&=n^3+\frac{3n^2}{2}+\frac{n}{2}\\
&=(n+1)(n+\frac{1}{2})n\\
&\\
&f(n)=\frac{n(n+1)(n+\frac{1}{2})}{3}
\end{aligned}
通过此方法，我们可以从 n+1 次幂推出 n 次幂！！！
你可以试着推一推其他更高次幂的求和。
好，接下来回归题目：
从 1 到 \sqrt{R} 枚举 x ，那 y 的最大值为 \sqrt{R-x^2} ，因为再大会超出这个圆。
当然 y 向下取整。
相加即可。
```c++
#include <bits/stdc++.h>
#define int long long
#define le double
#define mod 1000000007
using namespace std;
inline int qpow (int a, int b) {
int res = 1;
while (b) {
(b & 1) and (res = res * a % mod);
a = a * a % mod;
b >>= 1;
}
return res;
}
int r, ans, k, inv;
signed main () {
inv = qpow (6, mod - 2);
// 在取模情况下，除法最好使用逆元
cin >> r;
for (int x = 0, y; x * x <= r; x++) {
y = sqrt ((le) r - x * x);
k = (y * (y + 1) % mod * (y * 2 % mod + 1) % mod) * inv % mod + (x * x % mod * y % mod) % mod;;
ans = (ans + k) % mod;
}
cout << ans * 4 % mod;
}
```