python - 如何确定 N 的 d-redigit 倍数是否存在？

问题描述

我有以下问题：

我有 2 个自然正数：d 和 N。我需要找到最小 d-redigit 的长度，它是 N 的倍数。

如果 x 是 d 的序列，则自然数 x 是 d-redigit。示例：111111 是一个 1 位重位。

可能没有 N 的 d-redigit 倍数。

当我知道存在 N 的倍数的 d-redigit 时，我知道如何解决该问题。但是，我的问题是：如何确定这个 d-redigit，N 的倍数是否存在？

注意：这个实现的编程语言并不重要，它可以是伪代码，最好是 GCL。

我在 Python 中尝试了以下实现：

def proyect_a(n:int, d:int):
    if n == 0 or d == 0:
        return ''
    i = 1
    red = d
    while i < 11 and red%n != 0:
        red = 10*red + d
        i+=1
    if i < 11:
        return len(str(red))
    else:
        return '*'

前面的算法是一个蛮力的部分解决方案，因为它不能真正告诉所有情况下最小 d-redigit 的长度。正如你所看到的，这个循环最多重复 10 次，因为我真的不知道如何检查是否存在 N 的 d-redigit 倍数。

标签： pythonalgorithmmath

首先，由于您只关心被整除n，因此无需使用大整数。只需在每一步计算repdigit模值即可。n对于的任何值repdigit，只有n的可能值repdigit % n，因此如果在迭代n后找不到倍数n，则可以确定不存在解。

但是您可以通过在计算值中查找重复周期来做得更好。最简单的方法是存储的每个连续值repdigit。如果一个值出现两次，那么这意味着您已经进入了一个重复循环并且没有解决方案。但是没有必要存储repdigit. 循环的每次迭代相当于计算a=10、c=d 和 m=n的线性同余生成器的下一个输出。如果您从零初始值开始，则输出序列将在最多 3 次迭代后进入一个重复循环。

通过一些数学推理，您可以进一步加快计算速度。您实际上要计算的是，以零为种子的 LCG 第二次输出零所需的迭代次数（使用参数 a,c,m = 10,d,n）。

例如，当 n 和 d 互质且 n 是 3 的幂时，此 LCG 将产生一个最大长度序列min_repdigit_multiple(n,d)，在这种情况下将等于 n。您可能还可以采取其他捷径。

def min_repdigit_multiple(n:int, d:int):
    #
    #   Returns the length of the smallest repdigit number divisible by n
    #   i.e. the smallest value of x such that ((10**x-1)*d//9) % n == 0
    #   If no solution exists, returns -1 instead
    #
    assert 0 < d <= 9, "d must be a single non-zero digit"
    #
    # Check for a maximal length LCG sequence
    from math import gcd
    if gcd(n,d) == 1:
        n0 = n
        while n0 % 3 == 0:
            n0 //= 3
        if n0 == 1:
            return n
    #
    i = 1
    repdigit = 0
    seen = set()
    while i <= n:
        repdigit = (10 * repdigit + d) % n
        if repdigit in seen:
            # We've been here before, so there is no solution
            return -1
        if repdigit == 0:
            # Success: repdigit is divisible by n
            return i
        # There's no point in storing more
        # than the first few values of repdigit
        if i < 4:
            seen.add(repdigit)
        i += 1
    return -1   # Searched all possible values without finding a solution

python - 如何确定 N 的 d-redigit 倍数是否存在？

问题描述

解决方案

推荐阅读