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-1}\equiv b\times a^{-1}\pmod{\frac{p}{(a,p)}}\)，因为此时 \(a\not\perp p\)，没有逆元。

递归求解，直到 \(a\perp 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;

}