發表新討論
#26012: modular inverse


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.89.50]
最後登入時間 ：
2025-09-24 12:11:30
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)

學校 : 南投縣立旭光高級中學
編號 : 68108
來源 : [114.42.176.221]
最後登入時間 ：
2025-10-04 22:52:03
f974. 我看你…完全是不懂喔 -- 第四屆簡單的小競賽
| From: [36.232.39.147] | 發表日期: 2021-07-11 15:59

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

#26251: Re:modular inverse


Xcode (Xcode)

學校 : 臺北市立建國高級中學
編號 : 156489
來源 : [220.129.22.151]
最後登入時間 ：
2025-09-02 19:50:39
f974. 我看你…完全是不懂喔 -- 第四屆簡單的小競賽
| From: [123.194.161.220] | 發表日期: 2021-07-27 17:52

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


me too

#53493: Re: modular inverse


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

學校 : 不指定學校
編號 : 313278
來源 : [118.232.20.104]
最後登入時間 ：
2025-09-26 18:37:40
f974. 我看你…完全是不懂喔 -- 第四屆簡單的小競賽
| From: [118.232.20.104] | 發表日期: 2025-09-14 19:10

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


me too

+1

ZeroJudge Forum