大勾股定理是勾股定理的推广:对任何正整数 n 存在 2n+1 个连续正整数,满足前 n+1 个数的平方和等于后 n 个数的平方和。例如对于 n=1有32+42= 52 ;n=2 有102 +112+122 =132+142等。给定 n,本题就请你找出对应的解。
输入格式:
输入在一行中给出正整数 n(≤104 )。
输出格式:
分两行输出满足大勾股定理的解,格式如下:
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
提示:
50%的数据:n <= 500
83%的数据:n <= 1000
100%的数据:n <= 10000

思路:刚开始还想暴力解一下,后来一看n能取到10^4,超时是肯定的了,把其他几项列举出来,会发现每次结果的开始项都为 (n(2*n+1)),于是题变得非常简单
例如:21=3
(23+1),10=2(22+1),3=1(2*1+1)

链接说明

#include <iostream>
#include<vector>
#include<cstdio>
#include <algorithm>
#include<string>
#include<queue>
#include<cstring>
#include<cmath>
#include<sstream>
#include<set>
#include<map>

using namespace std;
typedef long long ll;
const int K = 10000;    // 数组里每位代表1W
const int M = 300;       // 一共10位

int n,i,j;

int main()
{
    cin >> n;
    for (i = n * (2 * n + 1), j = 1; j <= n + 1; j++,i++)
    {
        cout << i<<"^2";
        if (j != n + 1)
            cout << " + ";
    }
    cout << " =" << endl; //后面提交发现格式错误,多了一个空格

    for (j = 1; j <= n; j++, i++)
    {
        cout << i << "^2";
        if (j != n)
            cout << " + ";
    }
}