PTA 520 钻石争霸赛 2021 大勾股定理 (15 分)【数学】

大勾股定理是勾股定理的推广：对任何正整数 $n$ 存在 $2n+1$ 个连续正整数，满足前 $n+1$ 个数的平方和等于后 $n$ 个数的平方和。例如对于 $n=1$ 有 $3^2+4^2=5^{}2$ ​​；$n=2$ 有 $10^2+11^2+12^2=13^2+14^2$​​ 等。给定 $n$ ，本题就请你找出对应的解。

输入格式：
输入在一行中给出正整数 $n$（$\le 10^4$​​）。

输出格式：
分两行输出满足大勾股定理的解，格式如下：

a[0]^2 + a[1]^2 + ... + a[n]^2 =
a[n+1]^2 + ... + a[2n]^2

其中解的数列 a[0] ... a[2n] 按递增序输出。注意行首尾不得有多余空格。

输入样例：

3

输出样例：

21^2 + 22^2 + 23^2 + 24^2 =
25^2 + 26^2 + 27^2

解法 数学

乍一看本题就有点来势汹汹，如果暴力求前 $n+1$ 个数的平方和，然后暴力求后 $n+1$ 个数的平方和……复杂度难以想象。

事实上，本题很简单，我们设 $A=a[0](A>0)$ ，大勾股定理可以表述为：对任何正整数 $n$ 存在一组 $2n+1$ 个从 $A$ 开始的连续正整数，满足前 $n+1$ 个正整数的平方和等于后 $n$ 个数的平方和，即为：
$$\begin{gathered} A^2+(A+1{)}^2+...+(A+n{)}^2 \\ =(A+n+1{)}^2+(A+n+2{)}^2+..+(A+2n{)}^2 \end{gathered}$$

前后抵消同类项（前 $n+1$ 项的后 $n$ 项与后式抵消），得到：
$$\begin{gathered} A^2 \\ =n^2+2\ast (A+1)\ast n+n^2+2\ast (A+2)\ast n+...+n^2+2\ast (A+n)\ast n \end{gathered}$$

继续推导：
$$A^2=n^3+2n(A+1+A+2+...+A+n)$$

接着运用等差数列求和的公式，计算得到：
$$A^2=n^3+n^2(2A+n+1)$$

接下来就很简单了，将所有项都移动到左侧，得到一个关于 $A$ 的一元二次方程：
$$A^2-2n^{2}A-2n^3-n^2=0$$

运用对应的求根公式：
$$x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$$

由于 $A>0$ ，取正根，所以有： $$\begin{gathered} A=\frac{2n^2+\sqrt{4n^4+4n^2+8n^3}}{2}=n^2+\sqrt{n^4+n^2+2n^3} \\ =n^2+n\sqrt{n^2+2n+1}=2n^2+n \end{gathered}$$

现在可以写出代码了。由于代码是比赛时随手写的，所以并不是很简洁，求 $A$ 的公式没有化到最简单，最后的两个用于输出的 for 循环可以合并：

#include <bits/stdc++.h>
using namespace std; 
long long n;
int main() {
    scanf("%lld", &n);
    long long n2 = n * n, n3 = n2 * n; 
    long long A = (n2 * 2 + sqrt((n2 * 2) * (n2 * 2) + 4 * (2 * n3 + n2))) / 2;
    for (int i = 0; i <= n; ++i) {
        if (i == 0) printf("%d^2", A + i);
        else printf(" + %d^2", A + i);
    }
    printf(" =\n");
    for (int i = n + 1; i <= 2 * n; ++i) {
        if (i == n + 1) printf("%d^2", A + i);
        else printf(" + %d^2", A + i);
    }
    return 0;
}