2025天梯赛模拟试题-L1-005 大勾股数
大勾股定理是勾股定理的推广:对任何正整数 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 存在 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(≤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,都存在 2n+1 个这样的数字使得等式成立,那么我们首先想一下能不能找中间的那个数字,也就是对于1来说是4,对2来说是12,对3来说是24……
欸再仔细分解一下呢?4 = 1 * 4 ;12 = 2 * 6; 24 = 3 * 8;
好像有点那味了,再细化一下呢?1 * 4 = 1 * (2 * 2) ;2 * 6 = 2 * (2 * 3);3 * 8 = 3 * (2 * 4)
相信到这大家都能看出来了,对于数字n来说,它形成的这个大勾股数的最中心数字就是 n * ( 2 * ( n + 1 ) )了。那么代码部分就很容易实现了,就绝对不会出现蛮力算平方和的时间超限的问题了。
代码参考:
希望对你有帮助!天梯赛加油!
#include<bits/stdc++.h>
using namespace std;
int main (){
int n;
cin >> n;
vector<int> res;
int x = ((n+1)*2)*n - n;
for(int i = 0 ; i < 2*n + 1 ; i ++){
res.push_back(x);
x++;
}
for(int i = 0 ; i < n + 1; i ++){
if(i == 0 ){
printf("%d^2 ",res[i]);
}
else{
printf("+ %d^2 ",res[i]);
}
if (i == n) cout << "=" << endl;
}
for(int i = n+1 ; i < 2*n + 1; i ++){
if(i == n+1 ){
if(n+1 == 2*n )
printf("%d^2",res[i]);
else
printf("%d^2 ",res[i]);
}
else if (i == 2*n){
printf("+ %d^2\n",res[i]);
}
else printf("+ %d^2 ",res[i]);
}
}
更多推荐
所有评论(0)