#include<iostream>
using namespace std;
__int64 mult( __int64 a, __int64 b, __int64 n)
{
if( !b ) return 0;
return ( mult( a, b >> 1 , n ) * 2 + a * ( b & 1 ) ) % n;
}
__int64 mod_pow( __int64 m,__int64 e,__int64 n)
{
__int64 rel = 1;
while ( e )
{
if ( e & 1 )
rel = mult ( rel , m , n );
m = mult( m, m, n );
e >>= 1;
}
return rel;
}
__int64 ext_gcd( __int64 a,__int64 b,__int64 &x, __int64 &y )
{
if ( ! b )
{
x = 1 ;
y = 0 ;
return a;
}
__int64 d = ext_gcd( b, a % b, x, y );
__int64 t = x;
x = y;
y = t - a / b * y;
return d;
}
__int64 gcd( __int64 a, __int64 b )
{
__int64 t ;
while ( b )
{
t = a ;
a = b ;
b = t % b ;
}
return a;
}
__int64 pollard( __int64 n )
{
__int64 x = 1.0 * rand() / RAND_MAX * n;
__int64 y = x, i = 1, k = 2 ;
while ( true )
{
i ++ ;
x = ( mult( x, x, n ) + 1 ) % n ;
__int64 d ;
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 *= 2 ;
}
}
return 1;
}
int main()
{
__int64 c, e, n, m, d, r;
srand(time(0));
while ( scanf("%I64d%I64d%I64d",&c,&e,&n) != EOF )
{
__int64 p = pollard( n );
__int64 fi_n = ( p - 1 ) * ( n / p - 1 );
ext_gcd( e, fi_n, d, r);
if( d < 0 ){
d %= fi_n; d += fi_n;
}
printf("%I64d\n",mod_pow( c, d, n ) );
}
return 0;
}
posted on 2009-08-26 13:35
Huicpc217 阅读(115)
评论(0) 编辑 收藏 引用 所属分类:
数论 、
模板