BZOJ 2480: Spoj3105 Mod (扩展BSGS算法，模板)
Description
已知数a,p,b，求满足a^x≡b(mod p)的最小自然数x。
Input
每个测试文件中最多包含100组测试数据。
每组数据中，每行包含3个正整数a,p,b。
当a=p=b=0时，表示测试数据读入完全。
Output
对于每组数据，输出一行。
如果无解，输出“No Solution”（不含引号），否则输出最小自然数解。
Sample Input
5 58 33 2 4 3 0 0 0
Sample Output
9 No Solution
HINT
100%的数据，a,p,b≤1e9。 2016.3.29新加数据一组 by 1430586275
思路：BSGS算法，需要注意这里没有保证(a,p)=1，因此不能直接使用BSGS算法。
我们称之为扩展BSGS算法…
但是其实并不是什么新东西，不过是几次gcd,将条件转化成满足BSGS算法的情况
1/* ***********************************************
2Author :111qqz
3Created Time :Mon 24 Jul 2017 08:54:25 PM CST
4File Name :2480.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;
34map<LL,LL>mp;
35LL a,b,p;
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 ( int 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",&a,&p,&b))
89 {
90 if (a==0&&b==0&&p==0) break;
91 LL ans = BSGS(a,b,p);
92 if (ans==-1) puts("No Solution");
93 else printf("%lld\n",ans);
94 }
95 #ifndef ONLINE_JUDGE
96 fclose(stdin);
97 #endif
98 return 0;
99}