hdu 2815 Mod Tree 高次方程，n不为素数

  1 Accepted   406MS   8576K   2379 B    C++/**
  2 这里加了一点限制，，大体还是一样的，，
  3  
  4 **/
  5 #include <iostream>
  6 #include <cstdio>
  7 #include <cmath>
  8 #include <cstring>
  9 #include <algorithm>
 10 using namespace std;
 11 long long a,b,n;
 12 const int maxn = 499991;
 13 bool Hash[maxn];
 14 long long val[maxn];
 15 long long idx[maxn];
 16 
 17 long long gcd(long long a,long long b){
 18     if(b==0)
 19         return a;
 20     return gcd(b,a%b);
 21 }
 22 
 23 void ex_gcd(long long a,long long b,long long &x,long long &y){
 24     if(b==0){
 25         x=1;
 26         y=0;
 27         return ;
 28     }
 29     ex_gcd(b,a%b,x,y);
 30     long long tmp= x-(a/b)*y;
 31     x = y;
 32     y = tmp;
 33     return ;
 34 }
 35 
 36 void Insert(long long id,long long num){
 37     long long k = num%maxn;
 38     while(Hash[k]&&val[k]!=num){
 39         k++;
 40         if(k==maxn) k = k-maxn;
 41     }
 42     if(!Hash[k]){
 43         Hash[k] = true;
 44         val[k] = num;
 45         idx[k] = id;
 46     }
 47     return;
 48 }
 49 
 50 long long found(long long num){
 51     long long k = num%maxn;
 52     while(Hash[k]&&val[k]!=num){
 53         k++;
 54         if(k==maxn) k-=maxn;
 55     }
 56     if(Hash[k]){
 57         return idx[k];
 58     }
 59     return -1;
 60 }
 61 
 62 long long baby_step(long long a,long long b,long long n){
 63     long long temp =1;
 64     long long i;
 65     for(i=0;i<=100;i++){
 66         if(temp==b%n) return i;
 67         temp = temp*a%n;
 68     }
 69     long long tmp,d =1,cnt=0;
 70     memset(Hash,false,sizeof(Hash));
 71     memset(val,-1,sizeof(val));
 72     memset(idx,-1,sizeof(idx));
 73 
 74     while((tmp=gcd(a,n))!=1){
 75         if(b%tmp)
 76             return -1;
 77         cnt++;
 78         n = n/tmp;
 79         b = b/tmp;
 80         d =d*a/tmp%n;
 81     }
 82     long long cur =1;
 83     long long m = ceil(sqrt(n+0.5));
 84     for(i=0;i<m;i++){
 85         Insert(i,cur);
 86         cur = cur*a%n;
 87     }
 88     long long x,y;
 89     for(i=0;i<m;i++){
 90         ex_gcd(d,n,x,y);
 91         x = x*b%n;
 92         x = (x%n+n)%n;
 93         long long k = found(x);
 94         if(k!=-1)
 95             return i*m+k+cnt;
 96         d = d*cur%n;
 97     }
 98     return -1;
 99 }
100 
101 int main()
102 {
103     while(scanf("%I64d%I64d%I64d",&a,&n,&b)==3){
104         if(b>=n){
105             printf("Orz,I can’t find D!
");
106             continue;
107         }
108         if(n==1){
109             printf("0
");
110             continue;
111         }
112         long long res = baby_step(a,b,n);
113         if(res==-1){
114             printf("Orz,I can’t find D!
");
115         }else{
116             printf("%I64d
",res);
117         }
118     }
119     return 0;
120 }