我先把N分解 算出T = (p-1)*(q-1) 
然后 使用扩展欧基理得 算出 E在模T下的的逆元 得到D
最后 我计算 C^D mod N 得到答案

but WA了一整天...

是不是有overflow?? 但我也考虑了


#include <iostream>
using namespace std;

__int64 gcd(__int64 a , __int64 b)
{
	if( b ) while( (a%=b) && (b%=a) );
	return a+b;
}
__int64 mulmod( __int64 u , __int64 v , __int64 z )
{
	if( v==1 ) return u%z;
	if( u==0 || v==0 ) return 0;
	return (((mulmod(u,v/2,z)*2)%z)+(mulmod(u,v%2,z)%z))%z;
}
__int64 pow_mod(__int64 a, __int64 p, __int64 n)
{
    __int64 k = 1;
    while(p > 1)
    {
        if(p&1) k = mulmod(k, a, n);
        a = mulmod(a, a, n); p >>= 1;
    }
    return mulmod(k, a, n);
}
__int64 myabs( __int64 x )
{
	return x>=0?x:(-x);
}
__int64 random(){
        __int64 a;
        a = rand();
        a *= rand();
        a *= rand();
        return a;
}
#define MAX 500
__int64 zz;
__int64 f(__int64 x){
	return mulmod(x,x,zz)+1;
}
__int64  small( __int64 x )
{
	__int64 i;
	for( i=2;i<64&& i<x;i++)
		if( x%i==0 ) return i;
	return 0;
}
__int64 pollard(__int64 n){
        __int64 i,  p, x,xx;
        __int64 tmp;
        tmp = small(n);
        if( tmp ) return tmp;
        zz = n;
        for(i=1;i<MAX;i++){
                x = i;
                xx = f(x)%n;
                p = gcd((xx-x+n)%n,n);
                while(p==1){
                        x = f(x)%n;
                        xx = f( f(xx)%n )%n;
                        p = gcd( (xx-x+n)%n,n)%n;
                }
                if(p==0)continue ;
                else return p;
        }
        return -1;
}
__int64 egcd( __int64 a , __int64 b )
{
	__int64 x=0,y=1;
	__int64 lastx=1,lasty=0;
	__int64 tmp,q;
	while( b!=0 ){
		tmp = b;
		q = a/b;
		b = a%b;
		a = tmp;
		tmp = x;
		x = lastx-q*x;
		lastx = tmp;
		tmp = y;
		y = lasty-q*y;
		lasty = tmp;
	}
	return lastx;
}

int main()
{
	__int64 C,E,N,T,D,z,ans;
	while( cin >>C>>E>>N ){
		z = pollard(N);
		T = (z-1)*(N/z-1);
		D = egcd(E,T);
		ans = pow_mod(C,D,N);
		cout << ans << endl;
	}
	return 0;
}