> #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应该会超的八

• Re:你这个能通过POJ的Compiler么？ (20) iamsleepy 2005-06-27 15:32:06