algorithm - 几何级数模运算

Question

我正在给一个系列的形式

1+r+r^2+r^3+r^4+r^5

我必须找到级数和的模数，即我必须找到这个值

[(r^n-1)/(r-1)]%M

(r^n-1)%M的值我可以很轻松的计算出来，但是问题是分母项怎么计算呢？ 如果 (r-1) 和 M 不是互素数，则反模不存在。

请帮助如何获得这个值的任何近似值或算法？

由于求和很大，不能直接计算。

Answer 1

大概您打算用快速求幂循环计算 r^n

E(r, 0) = 1
E(r, n) = E(r*r, n/2)         if n is even
          r * E(r*r, (n-1)/2) if n is odd.

我们可以为 1 + r + r^2 + ... + r^n 构造一个类似的直接递推。

F(r, 0) = 1
F(r, n) = (1 + r) * F(r*r, (n-1)/2)       if n is odd
          1 + (r + r*r) * F(r*r, (n-2)/2) if n is even.

当然，所有的计算都应该以 M 为模进行。