hdu 2815 Mod Tree (扩展BSGS算法)
题意：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}