s093.
模逆元練習
Content
在模運算的世界中，給定整數 $a$ 與質數 $p$。如果存在一個整數 $x$ 使得：
$$ax \equiv 1 \pmod p$$
則我們稱 $x$ 為 $a$ 在模 $p$ 下的模逆元。
本題的要求很簡單：給定多組 $a$ 與 $p$，請計算出滿足 $0 \le x < p$ 的最小正整數 $x$。如果該模逆元不存在，請輸出 No Inverse。
Input
輸入包含多組測試資料（EOF 結束）。
每組測試資料佔一行，包含兩個以空格分隔的正整數 $a$ 與 $p$。
-
$1 \le a \le 10^{12}$
-
$2 \le p \le 10^{12}$，且 $p$ 保證為質數。
Output
對於每組輸入，請輸出一行：
-
若模逆元存在，輸出最小非負整數 $x$。
-
若不存在，請輸出
No Inverse。
Sample Input
#1
3 11 10 17 14 7 1234567 1000000007
Sample Output
#1
4 12 No Inverse 989145189
測資資訊：
記憶體限制：
256
MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <10M
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <10M
Hint ：
費馬小定理可以處理模質數的情況
也可以用 EXGCD
出處:
ShanC
[管理者：
s10900156@nh
...
(ShanC)
]
| ID | User | Problem | Subject | Hit | Post Date |
|
沒有發現任何「解題報告」
|
|||||