Description
已知数 \(a,p,b\)，求满足 \(a^x\equiv b\pmod 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
\(a,p,b≤10^9\)
Solution
当 \(\gcd(a,q)\not\mid b\) 且 \(b\ne 1\) 时无解。
\[a^x\equiv b\pmod p\\
a^{x-1}\frac{a}{(a,p)}\equiv \frac{b}{(a,p)}\pmod{\frac{p}{(a,p)}}
\]
a^{x-1}\frac{a}{(a,p)}\equiv \frac{b}{(a,p)}\pmod{\frac{p}{(a,p)}}
\]
注意这里不能写成 \(a^{x-1}\equiv b\times a^{-1}\pmod{\frac{p}{(a,p)}}\)，因为此时 \(a\not\perp p\)，没有逆元。
递归求解，直到 \(a\perp p\)，此时式子的形式是
\[k\times(a^m)^i\equiv a^jb\pmod p
\]
\]
从 \(0\dots m\) 枚举 \(j\)，将 \(a^jb\) 的值存入 \(hash\) 表中，然后从 \(1\dots m\) 枚举 \(i\)，若表中存在 \(k\times (a^m)^i\)，则当前 \(i\times m-j\) 就是答案。
Code
#include <cmath>
#include <cstdio>
#include <tr1/unordered_map>
std::tr1::unordered_map<int,int> hash;
int read() {
int x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
return x;
}
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
void exbsgs(int a, int b, int p) {
if (p == 1 || b == 1) { puts("0"); return; }
int t = gcd(a, p), k = 0, c = 1;
while (t > 1) {
if (b % t) { puts("No Solution"); return; }
b /= t, p /= t, c = 1LL * c * a / t % p, t = gcd(a, p), ++k;
if (b == c) { printf("%d\n", k); return; }
}
int m = ceil(sqrt(p)); hash.clear(), hash[b] = 0;
for (int i = 1; i <= m; ++i) t = 1LL * t * a % p, hash[1LL * t * b % p] = i;
a = t, t = 1LL * t * c % p;
for (int i = 1; i <= m; ++i, t = 1LL * t * a % p)
if (hash.count(t)) { printf("%d\n", i * m - hash[t] + k); return; }
puts("No Solution");
}
int main() {
int a = read(), p = read(), b = read();
while (a) exbsgs(a % p, b % p, p), a = read(), p = read(), b = read();
return 0;
}