a289: Modular Multiplicative Inverse
Tags : 同餘 數論基礎
Accepted rate : 272人/373人 ( 73% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-11-11 08:34

Content

一整數a 對模數n之模反元素是指滿足以下公式的整數 b

a-1 ≡ b        (mod n)

也可以寫成以下的式子

ab ≡ 1        (mod n)                     

現在給定兩個數字a, n,求一個最小正整數 b,若不存在則輸出” No Inverse”

Input

有多筆測資,每組第一行有兩個數字 a, n,(1 ≦ a, n ≦ 100,000,000)

Output

一個最小正整數 b,若不存在則輸出” No Inverse”

Sample Input #1
79 62
96 47
49 28
Sample Output #1
11
24
No Inverse
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <10M
Hint :
Tags:
同餘 數論基礎
出處:
[管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
14135
asnewchien@g... (david)
a289
後續
784 2018-06-15 16:03