C++司模

Question

我要計算這個公式

[(pow(4, p) - 1)/3] % q 

我寫了一個函數pow返回4模Q的P-次方的結果，但我不能在這裏使用它。 我該怎麼辦？

P，Q是整數，且可能很大 - 高達1 000 000 000

在此先感謝。

Answer 1

計算pow(4, p) - 1模3*q，並將結果除以3.要執行冪運算，請使用Modular exponentiation算法。

編輯：這會給你整數除法（即舍入結果）。請參閱@ lisyarus在整數環中劃分的答案，模q。

如果q不能被3整除，那麼兩個答案都應該給出相同的結果，因爲pow(4, p) - 1總是可以被3整除，所以整數除法舍入不會發揮作用。如果q可以被3整除，則不存在乘法逆，只能使用這種方法。

Answer 2

這取決於你除以3的意思。如果它是正常的整數除法，似乎@interjay回答了這個問題。如果它在整數模p環中除以3，那麼比你應該找到3模p的倒數，如果它存在的話。