UC知道如何快速判定一个整数是不是两个完全平方数之和？
来源：百度知道 编辑：UC知道 时间：2024/06/08 04:41:49
这个方法对于很大的整数（0～10^12）仍然很慢……
具体题目参见
https://www.spoj.pl/problems/TWOSQRS/
谢谢，这个题我是这样做的：
完全平方数有如下几个性质（与此题有关）：
1.形如4n+2和4n+3型的整数一定不是完全平方数；
2.形如8n+2, 8n+3, 8n+5, 8n+6,8n+7型的整数一定不是完全平方数；
3.平方数的形式具有下列形式之一：16m,16m+1, 16m+4,16m+9。
所以一个数是两个完全平方数之和应有如下性质：
1.模4余3的数一定不是所求。
2.模8余3，6，7的数一定不是所求。
3.模16余3,6,7,11,12,14,15的数一定不是所求。
通过这3个条件可以滤过大部分的其他数，如果该数能通过这3个条件则进行您给出的判定过程。
这样做快了很多。
谢谢！
问题的本质还是要遍历的，只要限制一下遍历规则即可。
第一：对于给出的整数n,求起平方根为sqrtn=sqrt(n),查找和为它的两个完全平方数循环到【sqrtn】（不大于sqrtn的整数）；
第二：设两个数分别为a,b;起始遍历条件是：int a=(int)sqrtn;a递减
截至条件是a<【b】的时候；循环内中给出b的值double b=sqrt(n-a*a);
经过这样两步，问题可以简单许多。比如判断122=121+1=十一的平方+1的平方的时候，【sqrtn】=11=a;b=1;//完成判断。
a=10;b=根号下22(判断它不是整数后 4点几）舍去；
a=9;b=41的平方根.6.几。舍去。
a=8;b=58的平方根;七点几；舍去；
a=7;显然b>a;停止。
实例：
void dec(int num)
{double sqrtn=sqrt(num),temp;
for(int a=(int(sqrtn),b=0;a>=b;a--)
{ temp=sqrt(num-a*a);b=(int)temp;
if((temp-double(b)<=0.00001)
cout<<a<<","<<b<<"的平方和为;"<<num<<endl;
}
cout<<"查找完毕"<<endl;
}
以上代码编译通过。速度不 错哦。
问题的本质还是要遍历的，只要限制一下遍历规则即可。
第一：对于给出的整数n,求起平方根为sqrtn=sqrt(n),查找和为它的两个完全平方数循环到【sqrtn】（不大于sqrtn的整数）；
第二：设两个数分别为a,b;起始遍历条件是：int a=(int)sqrtn;a递减
截至