【题目链接】
http://poj.org/problem?id=2417
【算法】
Baby-Step,Giant-Step算法
【代码】
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; typedef long long ll; const ll INF = 1e15; const int MOD = 1e5 + 7; ll B,N,P,ans,tot; int head[MOD],nxt[MOD],v[MOD]; ll num[MOD]; inline ll power(ll a,ll n) { ll res = 1,b = a; while (n) { if (n & 1) res = res * b % P; b = b * b % P; n >>= 1; } return res; } inline void clear() { tot = 0; memset(head,0,sizeof(head)); } inline void insert(ll val,int j) { int h = val % MOD; tot++; num[tot] = val; v[tot] = j; nxt[tot] = head[h]; head[h] = tot; } inline int query(ll val) { int i,h = val % MOD; for (i = head[h]; i; i = nxt[i]) { if (num[i] == val) return v[i]; } return -1; } inline ll Baby_Step_Giant_Step(ll B,ll N,ll P) { int i,j,t; ll val,ans = INF; clear(); B %= P; t = (int)sqrt(P) + 1; for (j = 0; j <= t; j++) { val = N * power(B,j) % P; insert(val,j); } B = power(B,t); if (B == 0) return N == 0 ? 1 : -1; for (i = 0; i <= t; i++) { val = power(B,i); j = query(val); if (j >= 0 && i * t - j >= 0) return i * t - j; } return -1; } int main() { while (scanf("%lld%lld%lld",&P,&B,&N) != EOF) { ans = Baby_Step_Giant_Step(B,N,P); if (ans == -1) printf("no solution "); else printf("%lld ",ans); } return 0; }