505022 - 扩展BSGS

【题目描述】扩展BSGS(ExBSGS)

给定a,p,b,求满足 ax≡b(mod p)的最小自然数x。

输入

包含若干组测试数据,保证∑sqrt(p)≤5×10^6。 每组数据中,每行包含3个正整数a,p,b(1≤a,p,b≤10^9或a=p=b=0)。 当a=p=b=0时,表示测试数据读入完全。

输出

对于每组数据,输出一行。 如果无解,输出“No Solution”,否则输出最小自然数解。

样例

输入

 5 58 33
2 4 3
0 0 0

输出

9
No Solution
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题