等比級數和：(xⁿ⁺¹-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 * (b^r(mod)-1) % m

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

至於b^r(mod)-1 mod m 可以用快速冪加速

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

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

me too