number-theory - 计算几何级数之和 (mod m)

Question

我有一个系列

S = i^(m) + i^(2m) + ...............  + i^(km)  (mod m)   

0 <= i < m, k may be very large (up to 100,000,000),  m <= 300000

我想求总和。我无法应用几何级数 (GP) 公式，因为这样结果将具有分母，然后我将必须找到可能不存在的模逆(如果分母和 m 不是互质)。

所以我做了一个替代算法，假设这些幂将使一个周期的长度远小于 k (因为它是一个模方程，所以我会得到类似 2,7,9,1,2,7 ,9,1....) 并且该循环将在上述系列中重复。因此，我不会从 0 迭代到 k，而是只求一个循环中的数字之和，然后计算上述系列中的循环数并将它们相乘。所以我首先找到了i^m (mod m)，然后一次又一次地乘以这个数字，并在每一步取模，直到再次到达第一个元素。

但是当我实际编写算法时，对于 i 的某些值，我得到了非常大的循环。因此在终止之前花费了大量时间，因此我的假设是不正确的。

那么我们还能发现其他模式吗？ (基本上我不想迭代 k。)因此，请给我一个求和的有效算法的想法。

Answer 1

这是我遇到的类似问题的算法

您可能知道可以在对数时间内计算一个数字的幂。您也可以这样做来计算几何级数的总和。因为它认为

1 + a + a^2 + ... + a^(2*n+1) = (1 + a) * (1 + (a^2) + (a^2)^2 + ... + (a^2)^n),

可以递归计算右边的几何级数即可得到结果。

这样您就不需要除法，因此您可以将总和(以及中间结果)的余数对您想要的任何数字取模。