如何快速判定一个整数是不是两个完全平方数之和?
题目
如何快速判定一个整数是不是两个完全平方数之和?
如题.
这个方法对于很大的整数(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的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
热门考点
- 美国的金融危机对我国的经济发展带来了不利因素,所以我们不应该坚持对外开放政策.
- 等腰梯形的面积为160cm2,上底比高多4cm,下底比高多20cm,求这个等腰梯形的高.
- 英语翻译
- 两个小数相乘,乘积四舍五入后是60.0这两个数都只是一小数且俩树的证书部分都是7.这两个小数的乘积四舍五入前是多少?
- 九年级上册英语一单元Reading原文
- 地球的天然卫星是什么?
- (1-cosx+sin3x),x趋近0时,求无穷小的主部
- 在数列{an}中,a1=1,a(n+1)=an/(3an+1),n属于N*,求其通项公式
- 一道逻辑题,小陈并非既懂英语又懂法语,如果上述断定为真,那么下属哪项断定必定为真?
- 琳琳写了120个字,比莉莉多写了96个,从今开始,玲玲写13个,莉莉写25个,几天后莉莉的总数将会比玲玲多96个.