發表新討論
#26012: modular inverse


fire5386 (becaidorz)

f974. 我看你…完全是不懂喔 -- 第四屆簡單的小競賽 | From: [111.243.16.106] | 發表日期: 2021-07-11 15:42

等比級數和：(xn+1-1) / (x-1)

因為除法沒有同餘性質，我們要找模反元素

如果要計算36 / 6 mod 17，可以變成36 * 6-1 mod 17

至於模反元素怎麼找呢？

令r(n)為小於n且跟n為互質的數量，r(4)=2，r(17)=16

a / b mod m = a * (br(mod)-1) % m

因為本題的mod為質數，所以r(mod)-1=mod-2

至於br(mod)-1 mod m 可以用快速冪加速

#26013: Re:modular inverse


asnewchien@gmail.com (david)

f974. 我看你…完全是不懂喔 -- 第四屆簡單的小競賽 | From: [36.232.39.147] | 發表日期: 2021-07-11 15:59

我看到戴眼鏡那個人，直接上一頁。

#26251: Re:modular inverse


Xcode (Xcode)

f974. 我看你…完全是不懂喔 -- 第四屆簡單的小競賽 | From: [123.194.161.220] | 發表日期: 2021-07-27 17:52

我看到戴眼鏡那個人，直接上一頁。


me too

#53493: Re: modular inverse


21422@chc.edu.tw (殷沒牙)

f974. 我看你…完全是不懂喔 -- 第四屆簡單的小競賽 | From: [118.232.20.104] | 發表日期: 2025-09-14 19:10

我看到戴眼鏡那個人，直接上一頁。


me too

+1

ZeroJudge Forum