1 Accepted    8508K    391MS    C++   2004B  2 相比下边，，优化太多太多了。。。  3 /**  4 baby-step-giant-step  因为数据量太大，，自己写hash  5   6 **/  7 #include 
     
        8 #include 
      
         9 #include 
       
         10 #include 
        
          11 using namespace std; 12 long long n,a,b; 13 const int maxn = 499991; 14 bool Hash[maxn]; 15 long long idx[maxn]; 16 long long val[maxn]; 17  18 void ex_gcd(long long a,long long b,long long &x,long long &y){ 19     if(b==0){ 20         x=1; 21         y=0; 22         return ; 23     } 24     ex_gcd(b,a%b,x,y); 25     long long tmp = x-(a/b)*y; 26     x = y; 27     y = tmp; 28 } 29  30 long long euler(long long n){ 31     long long i,tmp = n; 32     for(i=2;i*i<=n;i++)if(n%i==0){ 33         tmp = tmp/i*(i-1); 34         while(n%i==0) 35             n = n/i; 36     } 37     if(n>1) 38         tmp = tmp/n*(n-1); 39     return tmp; 40 } 41  42 void Insert(long long id,long long num){ 43     long long k = num%maxn; 44     while(Hash[k]&&val[k]!=num){ 45         k++; 46         if(k==maxn) k = k-maxn; 47     } 48     if(!Hash[k]){ 49         Hash[k] =1; 50         idx[k] = id; 51         val[k] = num; 52     } 53 } 54  55 long long found(long long num){ 56     long long k = num%maxn; 57     while(Hash[k]&&val[k]!=num){ 58         k++; 59         if(k==maxn) k = k-maxn; 60     } 61     if(!Hash[k]){ 62         return -1; 63     } 64     return idx[k]; 65 } 66  67 long long baby_step(long long a,long long b,long long n){ 68     long long m = ceil(sqrt(euler(n)+0.5)); 69     memset(Hash,false,sizeof(Hash)); 70     memset(idx,-1,sizeof(idx)); 71     memset(val,-1,sizeof(val)); 72     long long d=1; 73     for(long long i=0;i
         
          110 #include 
          
           111 #include 
           
            112 #include