b080: 模逆元(非$質數$版)
Tags :
Accepted rate : 3人/4人 ( 75% ) [非即時]
評分方式:
Special

最近更新 : 2022-09-16 20:17

Content

給定 $n$ 個數 $k_i$ 及 $P$,

計算 $k_i$ 對 $P$ 之模逆元

Input

第一行有兩個數 $n$, $P$

第二行有 $n$ 個數 $k_1$, $k_2$,..., $k_n$

$n ≤ 10^5$, $k_i<10^9$ , $p<10^9$

 

Output

輸出 $n$ 行,第 $i$ 行為 $k_i$ 的模逆元,若有多組解,輸出滿足 $0<k_i<p$ 之其中一解即可,若不存在,輸出 $-1$

Sample Input #1
3 3
9999999 123456 20150413
Sample Output #1
-1
-1
1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (6%): 0.7s , <1M
公開 測資點#1 (6%): 0.7s , <1M
公開 測資點#2 (6%): 0.7s , <1M
公開 測資點#3 (6%): 0.7s , <1M
公開 測資點#4 (6%): 0.6s , <1M
公開 測資點#5 (6%): 0.6s , <1M
公開 測資點#6 (6%): 0.6s , <1M
公開 測資點#7 (6%): 0.6s , <1M
公開 測資點#8 (6%): 0.6s , <1M
公開 測資點#9 (6%): 0.6s , <1M
公開 測資點#10 (6%): 0.6s , <1M
公開 測資點#11 (6%): 0.6s , <1M
公開 測資點#12 (7%): 0.6s , <1M
公開 測資點#13 (7%): 0.6s , <1M
公開 測資點#14 (7%): 0.6s , <1M
公開 測資點#15 (7%): 0.6s , <1K
Hint :
Tags:
出處:
臺中一中電腦資訊研習社 [管理者:
Ching367436 (Ching367436)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」