幾何系列模運算

Question

我給了一系列的

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

形式我必須找到系列即的總和的模數我一定要找到這個數值

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

我可以很容易計算(r^n-1)%M的值，但問題是如何計算分母項？ 因爲如果兩個(r-1) and 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. 

當然，所有的計算都應該完成mod M。