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 }