a157. Q-2-8. 模逆元(補充題)

內容

Modular multiplicative inverse，就是在模運算下的乘法反元素，有些人稱為「模反元素」或「模逆元」。

對於任何一個正整數a，它的模P乘法反元素就是滿足(a * b) % P = 1 的整數b，這裡的 % 就是取餘數運算。

計算a的模逆元是一個很重要的運算也有許多運用，最簡單的方法是窮舉測試：

輸入n 個正整數，以及一個質數P，請計算每一個輸入數的模逆元。

輸入的正整數的大小不超過P，P<=1000000009，0 < n < 10。

輸入說明

第一行是 n 與 P ，第二行 n 個整數同行數字以空白間隔

輸出說明

依照輸入順序輸出每一個數的模逆元，相鄰數字間間隔一個空白。

範例輸入 #1

3 7
3 4 1

範例輸出 #1

5 2 1

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1K
公開測資點#3 (20%): 1.0s , <1K
公開測資點#4 (20%): 1.0s , <1K

提示：

窮舉法的問題在於效率太差。在許多運用場合P是一個質數，而且探討的整數範圍都只在0 ~ P-1。在這些假設下有一個重要的數學性質可以幫助我們快速的計算模逆元(費馬小定理)：「若P為質數，對任意正整數a，(a^P-2 % P)是a在[1, P-1]區間的唯一乘法反元素。」根據此性質搭配快速冪就可以用O(log(P))個運算計算出模逆元。

標籤:

Modular multiplicative inverse

出處:

AP325 [管理者：

iris@stu.cch... (iris)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」