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的倒数，如果它存在的话。