- 平方之和2级1 2024.6
-
240714zj张逸凡 (张逸fan) LV 8 @ 2024-07-18 21:17:46
#include<bits/stdc++.h>
using namespace std;
long long n,a[100005],f,sum=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
f=0;
sum=0;
for(int j=1;j<=a[i];j++)
{
for(int m=1;m<=a[i];m++)
{
sum=j*j+m*m;
if(a[i]==sum)
f++;
}
}
if(f==0)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
}
2 条评论
-
240714zj张逸凡 (张逸fan) LV 8 @ 2024-07-19 23:29:58
栓Q
-
@ 2024-07-19 16:03:44
你三层循环，最坏条件时间复杂度10*10^6*10^6，肯定炸了
#include<bits/stdc++.h> using namespace std; long long n,a[100005],f,sum=0; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { f=0; sum=0; for(int j=1;j<=a[i];j++) { sum=a[i]-j; if(sum&&(floor(sqrt(sum))==sqrt(sum))&&(floor(sqrt(j))==sqrt(j))) { f++; break; } } if(f==0) cout<<"No"<<endl; else cout<<"Yes"<<endl; } return 0; }这是你的代码，我改了一下，把一层循环去掉了。其实只要里面一层循环穷举一个数,那么另一个数就是ai-xx,然后判断它俩是不是完全平方数就行了。另外你return 0忘加了,给你补上了。
-
@ 2024-07-19 16:04:48
#include<bits/stdc++.h> #define int long long using namespace std; inline void read(int &x) { x=0;int y=1;char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')y=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=y; } int n,x,tool[5005],tot; map<int,bool>mp; bool f; signed main() { for(int i=1;;i++) { if(i*i>1000000)break; tool[++tot]=i*i; mp[i*i]=1; } read(n); for(int i=1;i<=n;i++) { f=0; read(x); for(int i=1;i<=tot;i++) if(mp[x-tool[i]]) { cout<<"Yes"<<endl,f=1; break; } if(!f)cout<<"No"<<endl; } return 0; }这是我打的，时间复杂度更低一些，你糠糠
-
- 1
信息
- ID
- 2773
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 249
- 已通过
- 46
- 通过率
- 18%
- 上传者
-
金老师 (zfkin)
