用我的程序求模数为 10^9+7 的几何序列之和

Question

问题如下：输出(A^1+A^2+A^3+...+A^K)模1,000,000,007的答案，其中1≤A，K≤10^9，A和K必须为整数。

我正在尝试编写一个程序来计算上述问题。我试过使用几何序列的公式，然后对答案应用模数。由于结果也必须是整数，因此不需要求模逆。

下面是我现在的代码，它是 pascal

Var
a,k,i:longint;
power,sum: int64;
Begin
    Readln(a,k);
    power := 1;
    For i := 1 to k do
    power := ((power mod 1000000007) * a) mod 1000000007;
    sum := a * (power-1) div (a-1);
    Writeln(sum mod 1000000007);
End.

这个任务来自我的学校，他们不会把他们的测试数据泄露给学生。因此，我不知道我的程序为什么或哪里出错了。我只知道我的程序为他们的测试数据输出了错误的答案。

Answer 1

如果您想在不计算模逆的情况下执行此操作，可以使用以下方法递归计算：

1+ A + A² + A³ + ... + A^k

= 1 + (A + A²)(1 + A² + (A²)² + ... + (A²)^k/2-1)

偶数 k。对于奇数 k:

1+ A + A² + A³ + ... + A^k

= (1 + A)(1 + A² + (A²)² + ... + (A²)^(k-1)/2)

由于在每次递归调用中将k除以2，因此生成的算法具有O(log k)的复杂度。在 java:

static int modSumAtoAk(int A, int k, int mod)
{
    return (modSum1ToAk(A, k, mod) + mod-1) % mod;
}

static int modSum1ToAk(int A, int k, int mod)
{
    long sum;
    if (k < 5) {
        //k is small -- just iterate
        sum = 0;
        long x = 1;
        for (int i=0; i<=k; ++i) {
            sum = (sum+x) % mod;
            x = (x*A) % mod;
        }
        return (int)sum;
    }
    //k is big
    int A2 = (int)( ((long)A)*A % mod );
    if ((k%2)==0) {
        // k even
        sum = modSum1ToAk(A2, (k/2)-1, mod);
        sum = (sum + sum*A) % mod;
        sum = ((sum * A) + 1) % mod;
    } else {
        // k odd
        sum = modSum1ToAk(A2, (k-1)/2, mod);
        sum = (sum + sum*A) % mod;
    }
    return (int)sum;
}

请注意，我一直非常小心地确保每个产品都是以 64 位完成的，并在每个产品之后减少模数。

通过一些数学运算，上面的内容可以转换为不需要任何存储的迭代版本：

static int modSumAtoAk(int A, int k, int mod)
{
    // first, we calculate the sum of all 1... A^k
    // we'll refer to that as SUM1 in comments below

    long fac=1;
    long add=0;

    //INVARIANT: SUM1 = add + fac*(sum 1...A^k)
    //this will remain true as we change k

    while (k > 0) {
        //above INVARIANT is true here, too

        long newmul, newadd;
        if ((k%2)==0) {
            //k is even.  sum 1...A^k = 1+A*(sum 1...A^(k-1))
            newmul = A;
            newadd = 1;
            k-=1;
        } else {
            //k is odd.
            newmul = A+1L;
            newadd = 0;
            A = (int)(((long)A) * A % mod);
            k = (k-1)/2;
        }
        //SUM1 = add + fac * (newadd + newmul*(sum 1...Ak))
        //     = add+fac*newadd + fac*newmul*(sum 1...Ak)

        add = (add+fac*newadd) % mod;
        fac = (fac*newmul) % mod;

        //INVARIANT is restored
    }

    // k == 0
    long sum1 = fac + add;
    return (int)((sum1 + mod -1) % mod);
}

用我的程序求模数为 10^9+7 的几何序列之和

Finding sum of geometric sequence with modulo 10^9+7 with my program

algorithm

math

pascal