c++ - 模量的重复循环

Question

有没有一种有效的方法来找到 1111.. ⁿ mod M 的值？
总是可以使用重复平方来找到
10 ⁰ mod M + 10 ¹ mod M + 10 ² mod M + 10 ³ mod M + ...10 ⁿ mod M
有比这更快的方法吗？

Answer 1

您可以使用几乎类似于平方求幂的算法来解决此问题。

首先，如果你有偶数个 1，你可以看到：

11111111 = 1111     * 10001
n ones     n/2 ones   (10^(n/2) + 1)

这使数量增加了一倍。还，

1111111 = 111111   * 10 + 1
n ones    n-1 ones

将这些观察结果形式化，并为方便起见将具有 n 个 111...1 的数字命名为 J(n)：

• 如果 n 是偶数，则 J(n) = (10^(n/2) + 1)J(n/2)。
• 如果 n 是奇数，J(n) = 10*J(n-1) + 1。

您可以使用这些递推式（加上通过平方计算 10^(n/2) 的求幂的实际实现）模 M 来计算 O(log(n)^2) 时间的结果。

这是一些实现这一点的C代码。int如果你想要一个大的M（你需要 M^2 来适应你的类型），你必须使用更长的类型而不是避免溢出。

#include <stdio.h>

// Computes a to the power of n modulo m.
int pow_mod_m(int a, int n, int m) {
    if (n == 0) { return 1; }
    if (n == 1) { return a; }
    if (n % 2 == 0) {
        int k = pow_mod_m(a, n/2, m);
        return (k * k) % m;
    }
    return (pow_mod_m(a, n-1, m) * a) % m;
}

// Computes J(n) modulo m
int j_mod_m(int n, int m) {
    if (n == 1) {
        return 1;
    }
    if (n % 2 == 0) {
        return (j_mod_m(n/2, m) * (1 + pow_mod_m(10, n/2, m))) % m;
    }
    return (j_mod_m(n-1, m) * 10 + 1) % m;
}

int main(int argc, char**argv) {
    for (int i = 1; i < 1000; i++) {
        printf("%d: %d\n", i, j_mod_m(i, 12345));
    }
    return 0;
}

Answer 2

如果 10 是幂零的（如果 M = 2^a * 5^b），则 10 的幂最终会达到 0，或者在某个点开始循环。（其实0,0,0...也是一个循环。）循环的长度可以大到M-1。因此计算幂直到观察到重复值，并使用简单的代数根据观察到的不同幂来收集项。

我相信这会将复杂度从 O(n) 降低到 O(M)，这显然是对大 n 的改进。