BSGS 算法要求 (a) 和 (p) 互质，但如果 (a) 和 (p) 不互质怎么办呢？
这时候我们就引入了 (EXBSGS) 算法。
还是求 (a^x equiv b pmod p) , 但 (p) 不一定是质数。
如果 (a) 和 (p) 互质的话，那么套用一下 (BSGS) 的模板就可以解决了。
现在我们的就需要把 (p) 变成和 (a) 互质。
设 (g = gcd(a,p)) ,则有：
({aover g} a^{x-1} equiv {bover g} (mod {pover g} ))
如果 (b \%) (g eq 0) 的话，此方程无解。
但如果 (a) 和 (pover g) 互质的话，我们可以用 (BSGS) 算法求出一个解来。
反之继续递归下去，直到 (a) 和 (p) 互质即可。
同时在递归的时候，统计一下迭代的次数 (k)，那么最后方程的解即为 (k + t) ( (t) 为 (BSGS) 求出来的解)。
要注意的一点是当 ({a over g} = b) 的时候，这时候我们不用继续向下递归下去，此时 (x = k) 就是原方程的一组解。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
#define int long long
int a,b,p;
int gcd(int a,int b)
{
if(b == 0) return a;
else return gcd(b,a%b);
}
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
int ksm(int a,int b)
{
int res = 1;
for(; b; b >>= 1)
{
if(b & 1) res = res * a % p;
a = a * a % p;
}
return res;
}
void exgcd(int a,int b,int &x,int &y)
{
if(b == 0)
{
x = 1;
y = 0;
return;
}
exgcd(b,a%b,y,x);
y -= a / b * x;
}
int inv(int a,int p)//求a在模p下的逆元
{
int x,y;
exgcd(a,p,x,y);
return (x % p + p) % p;
}
int BSGS(int k,int a,int b,int p)//ka^x = b (mod p)
{
b = b * inv(k,p) % p;
map<int,int> hash;
int m = (int) sqrt(p) + 1;
for(int i = 1; i <= m; i++)
{
b = b * a % p;//要一个一个的乘，否则会炸 long long
hash[b] = i;
}
a = ksm(a,m), b = 1;
for(int i = 1; i <= m; i++)
{
b = b * a % p;
int j = hash.find(b) == hash.end() ? -1 : hash[b];
if(j >= 0 && i * m - j >= 0) return i * m - j;
}
return -1;
}
int Exbsgs(int a,int b,int p)
{
int k = 1, num = 0;
while(gcd(a,p) != 1)//直到 a 和 p 互质可以用bsgs求出一组解来
{
int g = gcd(a,p);
if(b % g != 0) return -1;//无解的情况
k = k * (a/g) % p; num++;//统计迭代的次数
if(k == b) return num;//系数 k = d的时候 k就是原方程的一个解
p /= g; b /= g;
}
int tmp = BSGS(k,a,b,p);
return tmp == -1 ? -1 : tmp + num;
}
signed main()
{
while(1)
{
a = read(); p = read(); b = read();
if(a == 0 && b == 0 && p == 0) break;
int ans = Exbsgs(a,b,p);
if(ans == -1) printf("No Solution
");
else printf("%lld
",ans);
}
return 0;
}