大勾股定理是勾股定理的推广:对任何正整数 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 << " + "; } }