#include <stdio.h>
#include <stdlib.h>

_int64 GCD(_int64 m, _int64 n)
{
    if(m<2||n<2)
        return 1; 
    while(true)
    {
        m = m % n;
        if(m==0)
            return n;
        n = n % m;
        if(n==0)
            return m; 
    }       
}
_int64 rnd(_int64 n)
{
    _int64 r = rand();
    r = r>0?r:-r;
    return r%n;
}    
_int64 factoring(_int64 n)
{
    srand(rand());
    _int64 i=1,x0=rnd(n),y=x0,k=2,x1,d;
    while(true)
    {
        i++;
        x1 = (x0*x0-1)%n;
        d = GCD(y-x1,n);
        if(d!=1 && d!=n)
           return d;    
        if(i==k)
        {
            y = x0 = x1;   k = 2*k;
        }
        else
            x0 = x1;      
    }    
} 
_int64 c,e,n,p,q,d,m,t,i;

_int64 mod_ex(_int64 a, _int64 b,  _int64 n)
{
     _int64 d = 1;
     while(b>0)
     {
          if(b%2==1)
              d=(d*a)%n;
          b=b/2;
          a=(a*a)%n;
     }
     return d;
}
_int64 GCD_ADV(_int64 a, _int64 n, _int64 &x,_int64 &y)
{
    if(a<1 || n<1)
    {
        return -1;
    }    
    _int64 x1,y1,c,d,q,r,t;
    x = y1 = 0; y = x1 = 1; c = a; d = n;
    while(true)
    {
        q = c / d;
        r = c % d;
        if(r==0)
        {
            return d;
        }   
        c = d;  d = r;
        t = x1;  x1 = x;  x = t - q*x;
        t = y1;  y1 = y;  y = t - q*y;
    }    
    return 0;
}

_int64 mod_linear(_int64 a,_int64 b,_int64 n)
{
    _int64 d,x,y,e,i;
    d = GCD_ADV(a,n,x,y);
    e = (x*(b/d)) % n;
    if(e<0)
        e += n;  
    return e; 
}

int main()
{
    while(scanf("%I64d%I64d%I64d",&c,&e,&n)!=EOF)
    {
        p = factoring(n);//分解出质因子 
        q = n / p;     //另一个质因子 
        t = (p-1)*(q-1);
        d = mod_linear(e,1,t);  //解模线性方程 
        m = mod_ex(c,d,n);      // 模取蜜算法 
        printf("%lld\n",m);
    }    
    return 0;
}        

• UP！因为这个Submit 快一百次了 (2136) sunmoonstar_love 2005-06-26 21:10:37
  • 怎么说呢，你应该冷静一下，重新思考一下，这样会更好 (0) c0500448264 2005-06-26 21:14:37
    • 谢谢，先去魔兽了 (0) sunmoonstar_love 2005-06-26 21:17:16