maksyuki 发表于 oj 分类,标签:

Clever Y

Little Y finds there is a very interesting formula in mathematics:

XY mod Z = K

Given XYZ, we all know how to figure out K fast. However, given XZK, could you figure out Y fast?


Input data consists of no more than 20 test cases. For each test case, there would be only one line containing 3 integers XZK (0 ≤ XZK ≤ 109).
Input file ends with 3 zeros separated by spaces.


For each test case output one line. Write "No Solution" (without quotes) if you cannot find a feasible Y (0 ≤ Y < Z). Otherwise output the minimum Y you find.

Sample Input

5 58 33

2 4 3

0 0 0

Sample Output


No Solution


POJ Monthly--2007.07.08, Guo, Huayang


题目类型:形如 A ^ X = B (mod C)的高次同余方程

算法分析:直接按照A ^ X = B (mod C)的格式求解即可