505021 - 高次同余方程

【题目描述】高次同余方程(BSGS)

给定一个质数P,以及正整数A和B,求满足同余方程Ax≡B (mod P )的最小非负整数 x。

输入

多组数据,每组数据一行,分别为P(2≤P≤2^31),A(2≤A<P),B(1≤B<P)。

输出

每组数据输出一行,如果有多组解,输出最小的数。否则输出“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
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题