#include <iostream>
#include <cstdlib>
#include <ctime>


using namespace std;

long long c,e,n,d;

const long double capasize=1000000000;

long double myabs(long double a)
{
     if (a<0) return -a;
     else return a;
}

long long egcd(long long a,long long b,long long *x,long long *y)
{
     if(b==0)
     {
             *x=1;
             *y=0;
             return a;
     }
     else
     {
             long long t,temp=egcd(b,a%b,x,y);
             t=*x;
             *x=*y;
             *y=t-(a/b)*(*y);
             return temp;
     }
}


long long linemod(long long a,long long b,long long n)
{
     long long x,y;
     long long d=egcd(a,n,&x,&y);
     if(b%d!=0) cerr<<"ERROR!!\n";
     long long e=x*(b/d)%n;
     while(e<0)
     {
         e+=n/d;
         e%=n;
     }
     return e;               
}


long double mymod(long double x)
{
    long double temp=x/n,v=x/n;
    while(temp>capasize) temp=temp/10;
    long double t=long(temp);
    int a;
    while(v-temp>1) 
    {
      t*=10;
      temp*=10;
      a=long(temp-t);
      t+=a;
    }
    return  x-t*n;
}

long long work(long double c,long long d)
{
     if(d==1) return c;
     else
     {
         if(d%2)
         {
                long double x=work(c,d/2);
                x=mymod(x*x);
                x*=c;
                return mymod(x);
         }
         else
         {
                long double x=work(c,d/2);
                return mymod(x*x);
         }
     }
}

long long gcd(long long a,long long b)
{
     if(b==0) return a;
     else return gcd(b,a%b);     
}

long long pollard()
{
    srand((unsigned)time( NULL ));
    long long i=1,k=2;
    long double x0=rand();
    x0=mymod(myabs(x0*x0-rand()));
    long double y=x0,x1,d,b;
    while(true)
    {
        i++;
        x1 = mymod(myabs(x0*x0-rand()));
        d = gcd(myabs(y-x1),n);
        if((d>1)&&(d<n))
           return d;    
        if(i==k)
        {
            y = x0 = x1;   k = 2*k;
        }
        else
            x0 = x1;      
    }    
} 


int main(int argc, char *argv[])
{
    
    long double t;
    long long f;
    while(cin >>c)
    {
     cin >>e>>n;
     f=pollard();
     t=(f-1)*(n/f-1);
     d=linemod(e,1,t);
     cout <<work(c,d)<<endl;
  }
    return 0;
}

Pollard那里怎么写会比较快一点啊？用long long应该会超的八

• 你这个能通过POJ的Compiler么？ (2690) sunmoonstar_love 2005-06-27 13:35:30
  • Re:你这个能通过POJ的Compiler么？ (20) iamsleepy 2005-06-27 15:32:06
• 贴程序注释删多了 (2371) iamsleepy 2005-06-27 15:33:34
• 搞定了 (16) iamsleepy 2005-06-27 16:13:57