题目描述

对于$A^x≡B (mod C)$，已知$A,B,C$,其中$C$为素数且$A，C$互质，求最小的 $x$ 满足上述同余方程。

输入格式

多组测试数据,每组一行3个数依次为$C,A,B$。

输出格式

对于每组测试数据,输出一行一个数,表示最小的$x$。如果无解输出一行字符串“no solution”。

样例

5 2 1
5 2 2
5 2 3
5 2 4
5 3 1
5 3 2
5 3 3
5 3 4
5 4 1
5 4 2
5 4 3
5 4 4
12345701 2 1111111
1111111121 65537 1111111111

0
1
3
2
0
3
1
2
0
no solution
no solution
1
9584351
462803587

数据范围

$2≤A<C<2^{31},1≤B<C$

来源

• poj2417
• 信息学奥赛之数学一本通
• stong9070整理