如何快速判定一个整数是不是两个完全平方数之和?

如何快速判定一个整数是不是两个完全平方数之和?

题目
如何快速判定一个整数是不是两个完全平方数之和?
如题.
这个方法对于很大的整数(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个条件则进行您给出的判定过程.
这样做快了很多.
答案
问题的本质还是要遍历的,只要限制一下遍历规则即可.
第一:对于给出的整数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)
举一反三
已知函数f(x)=x,g(x)=alnx,a∈R.若曲线y=f(x)与曲线y=g(x)相交,且在交点处有相同的切线,求a的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
最新试题
热门考点

超级试练试题库

© 2017-2019 超级试练试题库,All Rights Reserved.