如何快速判定一个整数是不是两个完全平方数之和?
如何快速判定一个整数是不是两个完全平方数之和?
如题.
这个方法对于很大的整数(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个条件则进行您给出的判定过程.
这样做快了很多.