posts - 2,comments - 1,trackbacks - 0
#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,1113,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;
    
while1 ){
        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 阅读(235) 评论(0)  编辑 收藏 引用 所属分类: 数论模板

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理