Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：k^D=n(%p),求最小的D (1<=K, P, N<=10^9)
思路：出题人英文水平捉鸡。。。。
扩展BSGS算法即可，注意p>=n的时候显然是无解的，判掉。
1/* ***********************************************
2Author :111qqz
3Created Time :Mon 24 Jul 2017 09:43:41 PM CST
4File Name :2815.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34LL k,p,n;
35map<LL,LL>mp;
36LL ksm(LL a,LL b,LL p)
37{
38 LL res = 1LL;
39 while (b)
40 {
41 if (b&1) res = res * a % p;
42 b = b>>1LL;
43 a = a * a % p;
44 }
45 return res;
46}
47LL gcd( LL a,LL b){return b?gcd(b,a%b):a;}
48LL BSGS(LL a,LL b,LL p)
49{
50 a%=p;
51 b%=p;
52 // if (a==0&&b==0) return 0;
53 // if (a==0) return -1;
54 if (b==1) return 0;
55 int cnt = 0 ;
56 LL t = 1;
57 for (int g = gcd(a,p); g!=1 ; g = gcd(a,p))
58 {
59 if (b%g) return -1;
60 p/=g;
61 b/=g;
62 t=t*a/g%p;
63 cnt++;
64 if (b==t) return cnt;
65 }
66 mp.clear();
67 int m = ceil(sqrt(double(p)));
68 LL base = b ;
69 for ( LL i = 0 ; i < m ; i++)
70 {
71 mp[base] = i;
72 base = base * a % p;
73 }
74 base = ksm(a,m,p);
75 LL ret = t ;
76 for ( int i = 1 ; i <= m+1 ; i++)
77 {
78 ret = ret * base % p;
79 if (mp.count(ret)) return i*m-mp[ret]+cnt;
80 }
81 return -1;
82}
83int main()
84{
85 #ifndef ONLINE_JUDGE
86 freopen("./in.txt","r",stdin);
87 #endif
88 while (~scanf("%lld%lld%lld",&k,&p,&n))
89 {
90 if (n>=p)
91 {
92 puts("Orz,I can’t find D!");
93 continue;
94 }
95 if (p==1)
96 {
97 puts("Orz,I can’t find D!");
98 continue;
99 }
100 LL ans = BSGS(k,n,p);
101 if (ans==-1) puts("Orz,I can’t find D!");
102 else printf("%lld\n",ans);
103 }
104
105 #ifndef ONLINE_JUDGE
106 fclose(stdin);
107 #endif
108 return 0;
109}