对于[1 + 2a + 3a ^ 2 + 4a ^ 3 + .... + ba ^(b-1)] MOD M是否有任何O(logn)解？

Question

假设我们有一系列求和 s = 1 + 2a + 3a ^ 2 + 4a ^ 3 + .... + ba ^(b-1)

我需要找到MOD M,其中M是素数,b是相对大的整数.

我找到了一个O((log n)^ 2)分而治之的解决方案.其中,g(n)=(1 + a + a ^ 2 + ... + a ^ n)MOD M.

f(a,b)= [f(a,b/2)+ a ^ b/2*(f(a,b/2)+ b/2*g(b/2))] MOD M,其中b是偶数f(a,b)= [f(a,b/2)+ a ^ b/2*(f(a,b/2)+ b/2*g(b/2))+ ba( b-1)] MOD M,其中b是奇数

是否有针对此问题的O(log n)解决方案？

Answer 1

是.观察到,1 + 2a + 3a^2 + ... + ba^(b-1)在衍生物a的1 + a + a^2 + a^3 + ... + a^b.(正式权力系列的领域涵盖了很多这样的技巧.)我们可以用时间O(log b)算术运算中的双数自动微分来评估后者.像这样的东西:

def fdf(a, b, m):
    if b == 0:
        return (1, 0)
    elif b % 2 == 1:
        f, df = fdf((a**2) % m, (b - 1) / 2, m)
        df *= 2 * a
        return ((1 + a) * f % m, (f + (1 + a) * df) % m)
    else:
        f, df = fdf((a**2) % m, (b - 2) / 2, m)
        df *= 2 * a
        return ((1 + (a + a**2) * f) % m, (
            (1 + 2 * a) * f + (a + a**2) * df) % m)

答案是fdf(a, b, m)[1].注意使用链式法则,当我们从衍生去相对于a**2该导数来a.