poj 2417

  1 Accepted    8508K    391MS    C++   2004B
  2 相比下边，，优化太多太多了。。。
  3 /**
  4 baby-step-giant-step  因为数据量太大，，自己写hash
  5 
  6 **/
  7 #include <iostream>
  8 #include <cstdio>
  9 #include <cmath>
 10 #include <cstring>
 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<m;i++){
 74         Insert(i,d);
 75         d = d*a%n;
 76     }
 77     long long res =1;
 78     long long x,y;
 79     for(long long i=0;i<m;i++){
 80         ex_gcd(res,n,x,y);
 81         long long tmp = x*b%n;
 82         tmp = (tmp%n+n)%n;
 83         long long k = found(tmp);
 84         if(k!=-1){
 85             return (i)*m+k;
 86         }
 87         res = res*d%n;
 88     }
 89     return -1;
 90 }
 91 
 92 int main()
 93 {
 94     while(scanf("%I64d%I64d%I64d",&n,&a,&b)==3){
 95         long long res = baby_step(a,b,n);
 96         if(res==-1)
 97             printf("no solution
");
 98         else
 99             printf("%I64d
",res);
100     }
101     return 0;
102 }
103 
104 -----------------------------------分割线---------------------------------------
105 /**
106 高次方程。。。baby-step-giant-step 算法
107 Accepted   4592K4     516MS      C++1104B
108 **/
109 #include <iostream>
110 #include <cstdio>
111 #include <math.h>
112 #include <map>
113 using namespace std;
114 
115 long long powmod(long long a,long long b,long long n){
116     if(b==0)
117         return 1;
118     long long c =1;
119     while(b){
120         if(b&1)
121             c =c*a%n;
122         a =a*a%n;
123         b>>=1;
124     }
125     return c;
126 }
127 
128 long long logmod(long long a,long long b,long long n){
129     long long m,v,e=1,i;
130     m = ceil(sqrt(n+0.5));
131     //cout<<(double)(n-1)*1.0/m<<endl;
132     //long long m_n = powmod(a,m,n);
133     v = powmod(a,n-1-m,n);
134     map<long long ,long long >x;
135     x.clear();
136     x[1] =m;
137     for(i=1;i<m;i++){
138         e = e*a%n;
139         if(!x[e]) x[e]=i;
140     }
141     for(i=0;i<m;i++){
142         if(x[b]){
143             long long num = x[b];
144             x.clear();
145             return i*m+(m==num?0:num);
146         }
147         b = b*v%n;
148     }
149     return -1;
150 }
151 
152 int main()
153 {
154     long long a,b,n;
155     while(scanf("%I64d%I64d%I64d",&n,&a,&b)==3){
156         long long res = logmod(a,b,n);
157         if(res==-1)
158             printf("no solution
");
159         else
160             printf("%I64d
",res);
161     }
162     return 0;
163 }