计算几何级数之和(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),

您可以递归计算右侧的几何系列以获得结果.

这样你就不需要除法,所以你可以将所有和(以及中间结果)的余数取模为你想要的任何数字.

Answer 2

正如您所指出的那样,对任意模数m进行计算很困难,因为许多值可能没有乘法逆模m.但是,如果您可以通过精心选择的备用模组来解决它,则可以将它们组合起来以获得解决方案模块.

将因子m分解为p_1, p_2, p_3 ... p_n每个p_i都是不同素数的幂

由于每个p是不同的主要幂,它们是成对的互质.如果我们可以计算关于每个模数p_i的系列之和,我们可以使用中国剩余定理将它们重新组合成一个解modm.

对于每个素数模数,有两个微不足道的特殊情况:

如果i ^ m与0 mod一致p_i,则总和平均为0.

如果i ^ m与1 mod一致p_i,那么总和与k mod一致p_i.

对于其他值,可以将常用公式应用于几何序列的总和:

S = sum(j = 0到k,(i ^ m)^ j)=((i ^ m)^(k + 1)-1)/(i ^ m - 1)

TODO:证明(i ^ m - 1)是互质的,p_i或找到他们有一个非平凡的GCD的替代解决方案.希望这p_i是一个主要的力量,也是m的除数这一事实将会有所作为...如果p_i是我的除数.条件成立.如果p_i是素数(而不是素数幂),则应用特殊情况i ^ m = 1,或者(i ^ m - 1)具有乘法逆.

如果几何和公式对某些公式不可用p_i,则可以重新排列计算,因此您只需要从1迭代到1 p_i而不是1到k,利用条件重复的周期不超过p_i.

(由于你的系列不包含aj = 0 term,你想要的值实际上是S-1.)

这产生了一组同余mod p_i,它满足CRT的要求.将它们组合成解决方案模块的过程在上面的链接中描述,所以我在此不再重复.

Answer 3

这可以通过重复平方的方法来完成，如果你考虑一个变量，那就是O(log(k))时间或O(log(k)log(m))时间m。

一般情况下，a[n]=1+b+b^2+... b^(n-1) mod m可以通过以下方式计算：

1. a[j+k]==b^{j}a[k]+a[j]
2. a[2n]==(b^n+1)a[n]

第二个只是第一个的推论。

在你的情况下，b=i^m可以及时计算O(log m)。

以下 Python 代码实现了这一点：

def geometric(n,b,m):
    T=1
    e=b%m
    total = 0
    while n>0:
        if n&1==1:
            total = (e*total + T)%m
        T = ((e+1)*T)%m
        e = (e*e)%m
        n = n/2
        //print '{} {} {}'.format(total,T,e)
    return total

这一点魔法有一个数学原因 - 对定义的操作

(a,r)@(b,s)=(ab,as+r)

是关联的，规则 1 基本上意味着：

(b,1)@(b,1)@... n times ... @(b,1)=(b^n,1+b+b^2+...+b^(n-1))

当操作具有关联性时，重复平方总是有效的。在这种情况下，@运算符是O(log(m))时间，因此重复平方需要O(log(n)log(m))。

看待这个问题的一种方法是矩阵求幂：

[[b,1],[0,1]]^n == [[b^n,1+b+...+b^(n-1))],[0,1]]

您可以使用类似的方法来计算(a^n-b^n)/(a-b)模，m因为矩阵求幂给出：

[[b,1],[0,a]]^n == [[b^n,a^(n-1)+a^(n-2)b+...+ab^(n-2)+b^(n-1)],[0,a^n]]