> #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;
> }        

• 怎么说呢，你应该冷静一下，重新思考一下，这样会更好 (0) c0500448264 2005-06-26 21:14:37
  • 谢谢，先去魔兽了 (0) sunmoonstar_love 2005-06-26 21:17:16