几何级数模运算 [英] Geometric Series Modulus operation

问题描述

我以...的形式给出了一系列

I am giving a series in the form of

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

我必须找到一系列和的模数，即我必须找到该值

I have to find modulus of a sum of series i.e i have to find this value

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

我可以轻松地计算(r ^ n-1)％M 的值，但是问题是如何计算分母项?因为如果(r-1)和M 都不互质，则反模将不存在.

I can easily calculate the value of (r^n-1)%M , But the problem is how to calculate the denominator term ? Since Inverse modulo can not be exist if both (r-1) and M are not co prime.

请帮助获取任何近似值或算法的值?

Please help how to get this value any approximation or algorithm ?

由于总和非常大，所以我无法直接计算该值.

Since summation is very large, I can't calculate the value directly.

推荐答案

大概您打算使用快速指数递归来计算 r ^ n

Presumably you're proposing to compute r^n with the fast exponentiation recurrence

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 构建类似的直接递归.

We can construct a similar direct recurrence for 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 .

All calculations should be done mod M, of course.

这篇关于几何级数模运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！