HDU 2815 扩展baby step giant step 算法

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <cmath>
 5 #include <map>
 6 using namespace std;
 7 #define ll long long
 8 
 9 int q_pow(int a , int b , int mod)
10 {
11     ll ans = 1;
12     while(b)
13     {
14         if(b&1) ans =((ll)ans*a)%mod;
15         a = ((ll)a*a)%mod;
16         b>>=1;
17     }
18     return ans;
19 }
20 
21 int gcd(int a , int b)
22 {
23     if(b == 0)return a;
24     else return gcd(b,a%b);
25 }
26 
27 int ex_gcd(int a , int &x , int b , int &y)
28 {
29     if(b == 0){
30         x=1 , y=0;
31         return a;
32     }
33     int ans = ex_gcd(b , x , a%b , y);
34     int t = x;
35     x=y , y = t-a/b*y;
36     return ans;
37 }
38 
39 int inv(int a , int b , int mod)
40 {
41     int x , y , d;
42     d = ex_gcd(a , x , mod , y);
43     int e = (ll)x*b%mod;
44     return e<0?e+mod:e;
45 }
46 
47 int BabyStep(int A,int B,int C){
48     map<int,int> Hash;
49     ll buf=1%C,D=buf,K;
50     int i,d=0,tmp;
51     for(i=0;i<=100;buf=buf*A%C,++i)
52         if(buf==B) return i;
53     while((tmp=gcd(A,C))!=1)
54     {
55         if(B%tmp)return -1;
56         ++d;
57         C/=tmp;
58         B/=tmp;
59         D=D*A/tmp%C;
60     }
61     Hash.clear();
62     int M=(int)ceil(sqrt((double)C));
63     for(buf=1%C,i=0;i<=M;buf=buf*A%C,++i)
64         if(!Hash.count((int)buf))Hash[(int)buf]=i;
65     for(i=0,K=q_pow((ll)A,M,C);i<=M;D=D*K%C,++i)
66     {
67         tmp=inv(D,B,C);
68         if(tmp>=0&&Hash.count(tmp))return i*M+Hash[tmp]+d;
69     }
70     return -1;
71 }
72 int main()
73 {
74    // freopen("a.in" ,"r" , stdin);
75     int k , p , n;
76     while(scanf("%d%d%d" , &k , &p , &n) == 3)
77     {
78         if(n>=p){
79             puts("Orz,I can’t find D!");
80             continue;
81         }
82         int ans = BabyStep(k , n , p);
83         if(ans == -1) puts("Orz,I can’t find D!");
84         else printf("%d\n" , ans);
85     }
86     return 0;
87 }

  1 #include<iostream>
  2 #include<map>
  3 #include<cmath>
  4 #include <cstdio>
  5 using namespace std;
  6 typedef long long LL;
  7 const int maxn = 65535;
  8 struct hash{
  9     int a,b,next;
 10 }Hash[maxn << 1];
 11 int flg[maxn + 66];
 12 int top,idx;
 13 //hash值插入
 14 void ins(int a,int b){
 15     int k = b & maxn;
 16     if(flg[k] != idx){
 17         flg[k] = idx;
 18         Hash[k].next = -1;
 19         Hash[k].a = a;
 20         Hash[k].b = b;
 21         return ;
 22     }
 23     while(Hash[k].next != -1){
 24         if(Hash[k].b == b) return ;
 25         k = Hash[k].next;
 26     }
 27     Hash[k].next = ++ top;
 28     Hash[top].next = -1;
 29     Hash[top].a = a;
 30     Hash[top].b = b;
 31 }
 32 //hash值查找
 33 int find(int b){
 34     int k = b & maxn;
 35     if(flg[k] != idx) return -1;
 36     while(k != -1){
 37         if(Hash[k].b == b) return Hash[k].a;
 38         k = Hash[k].next;
 39     }
 40     return -1;
 41 }
 42 int gcd(int a,int b)
 43 {
 44     return b?gcd(b,a%b):a;
 45 }
 46 int ext_gcd(int a,int b,int& x,int& y)
 47 {
 48     int t,ret;
 49     if (!b){x=1,y=0;return a;}
 50     ret=ext_gcd(b,a%b,x,y);
 51     t=x,x=y,y=t-a/b*y;
 52     return ret;
 53 }
 54 int Inval(int a,int b,int n){
 55     int x,y,e;
 56     ext_gcd(a,n,x,y);
 57     e=(LL)x*b%n;
 58     return e<0?e+n:e;
 59 }
 60 int pow_mod(LL a,int b,int c)
 61 {
 62     LL ret=1%c;
 63     a%=c;
 64     while(b){
 65         if(b&1)ret=ret*a%c;
 66         a=a*a%c;
 67         b>>=1;
 68     }
 69     return ret;
 70 }
 71 int BabyStep(int A,int B,int C){
 72     top = maxn; ++ idx;
 73     LL buf=1%C,D=buf,K;
 74     int i,d=0,tmp;
 75     for(i=0;i<=100;buf=buf*A%C,++i)
 76         if(buf==B)return i;
 77     while((tmp=gcd(A,C))!=1){
 78         if(B%tmp)return -1;
 79         ++d;
 80         C/=tmp;
 81         B/=tmp;
 82         D=D*A/tmp%C;
 83     }
 84     int M=(int)ceil(sqrt(C+0.5));
 85     for(buf=1%C,i=0;i<=M;buf=buf*A%C,++i)
 86         ins(i,buf);
 87     for(i=0,K=pow_mod((LL)A,M,C);i<=M;D=D*K%C,++i){
 88         tmp=Inval((int)D,B,C);
 89         int w ;
 90         if(tmp>=0&&(w = find(tmp)) != -1) return i*M+w+d;
 91     }
 92     return -1;
 93 }
 94 int main(){
 95     int A,B,C;
 96     while(scanf("%d%d%d",&A,&C,&B)!=EOF){
 97         if(B>C){
 98             puts("Orz,I can’t find D!");
 99             continue;
100         }
101         int tmp=BabyStep(A,B,C);
102         if(tmp<0)
103             puts("Orz,I can’t find D!");
104         else printf("%d\n",tmp);
105     }
106     return 0;
107 }