3125

3125. 扩展BSGS

题目

给定整数 $a,p,b$。

求满足 $a^x≡b \pmod p$ 的最小非负整数 $x$。

输入格式

每个测试文件中最多包含 $100$ 组测试数据。

每组数据中，每行包含 $3$ 个整数 $a,p,b$。

当 $a=p=b=0$ 时，表示测试数据读入完全。

输出格式

对于每组数据，输出一行。

如果有 $x$ 满足该要求，输出最小的非负整数 $x$，否则输出 No Solution。

数据范围

$1 \le a,p \le 2^{31}-1$,

$0 \le b \le 2^{31}-1$

输入样例：

5 58 33
2 4 3
0 0 0

输出样例：

9
No Solution

题解