問(wèn)題描述：
給定一個(gè)數(shù)，問(wèn)它是否能夠表示成兩個(gè)整數(shù)的平方和。
解題思路：
費(fèi)馬平方和定理的表述是：奇素?cái)?shù)能表示為兩個(gè)平方數(shù)之和的充分必要條件是該素?cái)?shù)被4除余1。
于是一個(gè)素?cái)?shù)p = 4n+1或者p = 2則必定能表示成兩個(gè)平方數(shù)之和。
同樣可以推導(dǎo)出如果兩個(gè)數(shù)均能表示成兩個(gè)平方數(shù)之和，則他們的乘積必定能表示成兩個(gè)平方數(shù)之和：
p = a^2 + b^2;
q = c^2 + d^2;
p*q = (a^2 + b^2)(c^2 + d^2) = (ac)^2 + (ad)^2 + (bc)^2 + (bd)^2 = (ac + bd)^2 + (ac - bd)^2
只要將所求數(shù)分解素因子，然后對(duì)于每個(gè)素?cái)?shù)看是否滿足條件，一旦有一個(gè)素因子不滿足費(fèi)馬平方和定理則直接輸出"NO"，全部滿足則輸出"YES"
代碼如下：
#include <iostream>
#include <cstdlib>
#include <cmath>
#define gcc 10007
typedef __int64 Int;
#define MAX ((Int)1<<63)-1
using namespace std;
Int p[10] = 
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
Int Gcd(Int a, Int b)
{
Int m = 1;
while(m)
{
m = a % b;
a = b;
b = m;
}
return a;
}
//計(jì)算a*b%n
inline Int Produc_Mod(Int a, Int b, Int mod)
{
Int sum = 0;
while(b)
{
if(b & 1) sum = (sum + a) % mod;
a = (a + a) % mod;
b /= 2;
}
return sum;
}
//計(jì)算a^b%n
inline Int Power(Int a, Int b, Int mod)
{
Int sum = 1;
while(b)
{
if(b & 1) sum = Produc_Mod(sum, a, mod);
a = Produc_Mod(a, a, mod);
b /= 2;
}
return sum;
}
//Rabin_Miller判素
bool Rabin_Miller(Int n)
{
int i, j, k = 0;
Int u, m, buf;
//將n-1分解為m*2^k
if(n == 2)
return true;
if(n < 2 || !(n & 1))
return false;
m = n-1;
while(!(m & 1))
{
k++;
m /= 2;
}
for(i = 0; i < 9; i++)
{
if(p[i] >= n)
return true;
u = Power(p[i], m, n);
if(u == 1)
continue;
for(j = 0; j < k; j++)
{
buf = Produc_Mod(u, u, n);
//看是否有非平凡因子存在
if(buf == 1 && u != 1 && u != n-1)
return false;
u = buf;
}
//如果p[i]^(n-1) % n != 1 那么 n為合數(shù)
if(u-1)
return false;
}
return true;
}
Int Pollard_rho(Int n)
{
while(1)
{
int i = 1;
Int x = rand() % (n-1) + 1;
Int y = x;
Int k = 2;
Int d;
do{
i++;
d = Gcd(n + y - x, n);
if(d > 1 && d < n)
return d;
if(i == k)
y = x, k *= 2;
x = (Produc_Mod(x, x, n) + n - gcc) % n;
}while(y != x);
}
}
Int prime[10000];
int top;
void Prime_Divisor(Int key)
{
if( Rabin_Miller(key) )
{
prime[ top ++ ] = key;
}else
{
Int buf = Pollard_rho(key);
if( Rabin_Miller(buf) ){
prime[ top ++ ] = buf;
}else{
Prime_Divisor(buf);
}
if( Rabin_Miller(key / buf) ){
prime[ top ++ ] = key / buf;
}else{
Prime_Divisor(key / buf);
}
}
}
int main()
{
int t, i;
Int n;
scanf("%d", &t);
while(t--)
{
scanf("%I64d", &n);
if(n < 0)
printf("NO\n");
else if(n == 0 || n == 1)
printf("YES\n");
else
{
top = 0;
Prime_Divisor(n);
for(i = 0; i < top; i++)
if( prime[i] != 2 && (prime[i] - 1) % 4 )
break;
if(i < top)
printf("NO\n");
else
printf("YES\n");
}
}
}