3243 Clever Y

原文

時間制限:5000ミリ秒
メモリ制限:65536KB

問題

リトルＹは数学の興味深い式を見つけた。

X^Y mod Z = K
X,Y,Zが与えられたとき、Kを素早く見つける方法は分かる。しかし、X,Z,K (0 ≤ X, Z, K ≤ 109). が与えられたとき、Yを素早く見つける事はできるだろうか？

入力

入力は、２０個以下のテストケースで構成されている。それぞれのテストケースには、３つの整数X,Z,Kを含む一行のみが書かれている。入力ファイルはスペースで区切られた３つの０で終わる。

出力

それぞれのテストケースについて、一行を出力しなさい。当てはまる(0 ≤ Y < Z)が無い場合は"No Solution"を、そうでなければ当てはまるYのうち最も小さい物を出力しなさい。

入力の例

5 58 33
2 4 3
0 0 0

出力の例

9
No Solution

出典

POJ Monthly--2007.07.08, Guo, Huayang