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算法的情况
/* ***********************************************
Author :111qqz
Created Time :Mon 24 Jul 2017 08:54:25 PM CST
File Name :2480.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6map<LL,LL>mp;
7LL a,b,p;
8LL ksm(LL a,LL b,LL p)
9{
10 LL res = 1LL;
11 while (b)
12 {
13 if (b&1) res = res * a % p;
14 b = b>>1LL;
15 a = a * a % p;
16 }
17 return res;
18}
19LL gcd( LL a,LL b){return b?gcd(b,a%b):a;}
20LL BSGS(LL a,LL b,LL p)
21{
22 a%=p;
23 b%=p;
24 if (a==0&&b==0) return 0;
25 if (a==0) return -1;
26 if (b==1) return 0;
27 int cnt = 0 ;
28 LL t = 1;
29 for (int g = gcd(a,p); g!=1 ; g = gcd(a,p))
30 {
31 if (b%g) return -1;
32 p/=g;
33 b/=g;
34 t=t*a/g%p;
35 cnt++;
36 if (b==t) return cnt;
37 }
38 mp.clear();
39 int m = ceil(sqrt(double(p)));
40 LL base = b ;
41 for ( int i = 0 ; i < m ; i++)
42 {
43 mp[base] = i;
44 base = base * a % p;
45 }
46 base = ksm(a,m,p);
47 LL ret = t ;
48 for ( int i = 1 ; i <= m+1 ; i++)
49 {
50 ret = ret * base % p;
51 if (mp.count(ret)) return i*m-mp[ret]+cnt;
52 }
53 return -1;
54}
55int main()
56{
57 #ifndef ONLINE_JUDGE
58// freopen("./in.txt","r",stdin);
59 #endif
60 while (scanf("%lld%lld%lld",&a,&p,&b))
61 {
62 if (a==0&&b==0&&p==0) break;
63 LL ans = BSGS(a,b,p);
64 if (ans==-1) puts("No Solution");
65 else printf("%lld\n",ans);
66 }
67 #ifndef ONLINE_JUDGE
68 fclose(stdin);
69 #endif
70 return 0;
71}