如何快速判定一个整数是不是两个完全平方数之和?如题.这个方法对于很大的整数（0～10^12）仍然很慢……具体题目参见这个题我是这样_数学解答

如何快速判定一个整数是不是两个完全平方数之和?
如题.
这个方法对于很大的整数（0～10^12）仍然很慢……
具体题目参见
这个题我是这样做的：
完全平方数有如下几个性质（与此题有关）：
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个条件则进行您给出的判定过程.
这样做快了很多.

人气：413 ℃　时间：2020-06-27 20:22:25

解答

问题的本质还是要遍历的,只要限制一下遍历规则即可.
第一：对于给出的整数n,求起平方根为sqrtn=sqrt(n),查找和为它的两个完全平方数循环到【sqrtn】（不大于sqrtn的整数）；
第二：设两个数分别为a,b;起始遍历条件是：int a=(int)sqrtn;a递减
截至条件是aa;停止.
实例：
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)