#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<time.h>
using namespace std;
typedef unsigned long long llu;
int p[] = { 2,3,5,7,11, 13,17,19,23,29 };
int k = 10;
// 不适合时限较低的题目。常数非常大！！！
llu mol_mult( llu a, llu b, llu n)
{
if( !b ) return 0;
return ( mol_mult( a, b >> 1 , n ) * 2 + a * ( b & 1 ) ) % n;
}
/*
// 代码量大，但常数低
llu mol_mult( llu a,llu b,const llu &mol)
{
llu c = a >> 30 , d = b >> 30 , tmp , t;
tmp = 1ll << 30;
a %= tmp ; b %= tmp;
llu ans = a * b;
if( ans > mol )
ans %= mol;
tmp = c * b ;
if( tmp > mol ) tmp %= mol;
t = 30;
while( t -- ){
tmp <<= 1;
if( tmp > mol ) tmp -= mol;
}
ans += tmp;
if( ans > mol )
ans -= mol;
tmp = d * a ;
if( tmp > mol ) tmp %= mol;
t = 30;
while( t -- ){
tmp <<= 1;
if( tmp > mol ) tmp -= mol;
}
ans += tmp;
if( ans > mol )
ans -= mol;
tmp = d * c ;
if( tmp > mol ) tmp %= mol;
t = 60;
while( t -- ){
tmp <<= 1;
if( tmp > mol ) tmp -= mol;
}
ans += tmp;
ans %= mol;
return ans;
}
*/
llu mol_exp( llu a,llu b,llu n)
{
llu t = a % n , ans = 1;
while( b )
{
if( b & 1 )
{
ans = mol_mult( ans, t, n);//1ll * ans * t % n;
}
t = mol_mult( t, t, n );//1ll * t * t % n;
b >>= 1;
}
return ans;
}
int witness( llu a,llu n )
{
llu t = 0, tmp = n - 1;
while( tmp % 2 == 0 ){
t ++ ;
tmp >>= 1 ;
}
llu x0 = mol_exp( a, tmp, n ), x1, i;
for ( i = 1 ; i <= t ; i ++ )
{
x1 = mol_mult( x0, x0 , n);//1ll * x0 * x0 % n;
if( x1 == 1 && x0 != 1&& x0 != n - 1 )
return 1;
x0 = x1;
}
if( x1 != 1 )
return 1;
return 0;
}
inline llu my_rand(llu b,llu e )
{
return (llu)((1. * rand() / ( 1. + RAND_MAX ) * (e - b + 1))) + b;
}
int miller_rabin( llu n,llu s )
{
llu i, a;
for ( i = 1 ; i <= s ; i ++ )
{
a = my_rand( 2, n - 1);
if( witness ( a, n ) ) return 0;
}
return 1;
}
llu gcd(llu a,llu b){
llu t ;
while( b ){
t = a % b; a = b; b = t;
}
return a;
}
llu pollard_rho( llu n, llu c )
{
llu i = 1;
llu x = my_rand( 1, n - 1 ), d;
llu y = x;
llu k = 2;
while( 1 ){
i ++;
x = ( mol_mult( x , x, n ) + n - c ) % n;
if( x == y )
break;
if ( x > y )
d = gcd( x - y, n );
else
d = gcd( y - x, n );
if( d != 1 && d != n )
return d;
if( i == k ){
y = x;
k <<= 1 ;
}
}
return n;
}
llu minfactor;
void make(llu n)
{
llu d, c;
if( miller_rabin( n, 20 ) ){
minfactor = min( minfactor , n );
return ;
}
do{
c = my_rand( 1, n - 1 );
d = pollard_rho( n, c );
}while( d >= n );
make( d );
make( n/d );
}
int main()
{
llu n, i;
srand( n );
int test;
cin>>test;
while( test--)
{
cin>>n;
if( n == 1 ){ puts("1"); continue; }
for ( i = 0 ; i < k ; i ++ )
if( n % p[i] == 0 ){
if( n == p[i] )
puts("Prime");
else
printf("%d\n",p[i]);
break;
}
if( i < k ) continue;
minfactor = n;
if( miller_rabin( n, 20 ) )
printf("Prime\n");
else{
make( n );
printf("%llu\n",minfactor);
}
}
return 0;
}
posted on 2009-08-26 13:33
Huicpc217 阅读(226)
评论(0) 编辑 收藏 引用 所属分类:
数论 、
模板