题目
如何快速判定一个整数是不是两个完全平方数之和?
如题.
这个方法对于很大的整数(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个条件则进行您给出的判定过程.
这样做快了很多.
如题.
这个方法对于很大的整数(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个条件则进行您给出的判定过程.
这样做快了很多.
提问时间:2021-04-02
答案
问题的本质还是要遍历的,只要限制一下遍历规则即可.
第一:对于给出的整数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)
第一:对于给出的整数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的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
最新试题
- 1英语作文题:“Where to Live – in the Cityor in the Country?”
- 2“犹有花枝俏”和“俏也不争春”中的俏有和表达效果?
- 3The latest Census data reveal that that young people aged 25 to 29 are increasingly more mobile and
- 41米的丝带红剪了丝带的10分之3.3米的丝带军剪了丝带的10分之1谁剪下来丝带长?这两条丝带剩的部分一样吗
- 5MR liu______a public house a short time ago A has bought B bought C Was bought Dis bought
- 6英语翻译
- 7I consider that he is a selfish man是定语从句吗,表语定语状语主语系动词谓语动词分别是什么
- 8地球绕太阳公转每小时经过的路程约为1.1*10的5次方千米,声音在空气中每小时的空气中传播1.2*10的3次方千米,地球绕太阳转动的速度与声音传播的速度哪个快?
- 9观察水沸腾时的温度和沸腾后的温度是如何变化的.
- 10杜甫的诗广泛深刻地反映了什么?
热门考点
- 1关于质点的曲线运动,下列说法中不正确的是( ) A.曲线运动肯定是一种变速运动 B.变速运动必定是曲线运动 C.曲线运动可以是速率不变的运动 D.曲线运动可以是加速度不变的运动
- 2我们常用的数是十进制的数,计算机程序使用的是二进制数,它们两者间可以互化 如将1101换算成十进制数
- 3500米等于几公里拜托各位大神
- 4细胞内蛋白质的加工转运.
- 5乡村生活的优缺点英语作文
- 6食物中的非能量营养物质是( )( )
- 7go out of your way to be
- 8O为三角形ABC内一点,连接OB、OC说明角BOC与角A的大小关系(请写明详细步骤)
- 9Diana had to leave,_____said she would meet Susan in front of the theatre. A.but B.then
- 10若一个数与它的绝对值的商是-1,则这个数是?