题目描述
Little Y finds there is a very interesting formula in mathematics:
$$
X^Y \bmod Z=K
$$
Given $X, Y, Z$, we all know how to figure out $K$ fast. However, given $X, Z, K$, could you figure out $Y$ fast?
题意概述
给定$X, Z, K$，求满足$X^Y \bmod Z=K$的$Y$的最小值。若不存在$0 \le Y \lt Z$满足条件，则输出无解。
数据范围：$0 \le X, Z, K \le 10^9$。
算法分析
显然$K \ge Z$时无解。在其他情况下，条件可以写成
$$
X^Y \equiv K \pmod Z
$$
特殊处理两种情况：$X, K$中至少有一个为$0$时，$Y=1$或无解；$K=1$时，$Y=0$。
先考虑$(X, Z)=1$的情况。令$M=\lceil \sqrt{Z} \rceil, \; Y=aM-b \; (0 \lt a, b \le M)$，那么
$$
\begin{align}
X^{aM-b} &\equiv K \pmod Z \\
X^{aM} &\equiv K \cdot X^b \pmod Z
\end{align}
$$
可以在$O(M)$的时间内预处理出$K \cdot X^b$，存在哈希表中，接着$O(M)$枚举$a$，判断哈希表中是否存在$X^{aM}$，若存在，则找到解$Y=aM-b$。由于要求最小值，因此哈希表中有重复时应记录较大的$b$。
下面考虑$(X, Z) \gt 1$的情况。令$D=(X, Z)$，易知若$K \nmid D$则无解。设$X=Dx, \; K=Dk, \; Z=Dz$，据同余的性质可得
$$
\begin{align}
(Dx)^Y &\equiv Dk \pmod{Dz} \\
x \cdot (Dx)^{Y-1} &\equiv k \pmod z
\end{align}
$$
因为$D=(X, Z)$，所以$(x, z)=1$，即$x$在模$z$意义下有逆元，因此
$$
(Dx)^{Y-1} \equiv k \cdot x^{-1} \pmod z
$$
令$X’=Dx=X, \; Y’=Y-1, \; K’=k \cdot x^{-1}, \; Z’=z$，则
$$
(X’)^{Y’} \equiv K’ \pmod{Z’}
$$
这和初始时的方程具有一样的形式。若$(X’, Z’) \gt 1$，则重复以上过程，否则可以参照$(X, Z)=1$的情况。
代码
/*
* You will be singled out for promotion in your work.
*/
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
class HashTable {
private:
static int const MOD = 3214567;
int numr, h[MOD], id[MOD], val[MOD], nxt[MOD];
public:
void clear() { memset(h, numr = 0, sizeof h); }
int count(int const &n) {
for (int i = h[n % MOD]; i; i = i[nxt])
if (i[id] == n)
return 1;
return 0;
}
int &operator[](int const &n) {
for (int i = h[n % MOD]; i; i = i[nxt])
if (i[id] == n)
return i[val];
++numr, numr[id] = n, numr[nxt] = h[n % MOD], h[n % MOD] = numr;
return numr[val];
}
} mp;
int ex_gcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int ret = ex_gcd(b, a % b, y, x);
y -= a / b * x;
return ret;
}
int get_gcd(int a, int b) {
int x, y;
return ex_gcd(a, b, x, y);
}
int get_inv(int a, int b) {
int x, y;
return ex_gcd(a, b, x, y), (x + b) % b;
}
int bsgs(int a, int b, int c) {
a %= c;
if (a == 0)
return b == 0 ? 1 : -1;
if (b == 0)
return -1;
if (b == 1)
return 0;
int k = 0;
for (int t; (t = get_gcd(a, c)) > 1; ++k) {
if (b % t)
return -1;
c /= t, b /= t, b = 1ll * b * get_inv(a / t, c) % c;
}
mp.clear();
int d = a, m = sqrt(c) + 1;
for (int i = 1; i <= m; ++i, d = 1ll * d * a % c)
mp[1ll * d * b % c] = i;
d = 1ll * d * get_inv(a, c) % c;
int e = d;
for (int i = 1; i <= m; ++i, e = 1ll * e * d % c)
if (mp.count(e))
return i * m - mp[e] + k;
return -1;
}
int main() {
for (int a, b, c; scanf("%d%d%d", &a, &c, &b), a || b || c;) {
int ans = bsgs(a, b, c);
if (~ans)
printf("%d\n", ans);
else
puts("No Solution");
}
return 0;
}