模量的重复循环

Question

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

Answer 1

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

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

Answer 2

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

首先，如果你有偶数个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;
}

模量的重复循环

Repeating Cycle of Modulus

c++

algorithm

discrete-mathematics

modular-arithmetic