幾何シリーズモジュラス操作

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が両方ともcoプライムでない場合、逆モジュロは存在しないためです。

この値を近似値またはアルゴリズムとするにはどうすればよいですか？

合計が非常に大きいため、値を直接計算することはできません。

Answer 1

おそらくあなたは私たちが1 + r + r^2 + ... + 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. 

で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を実行する必要があります。