如何确定N的数字倍数的存在性？

Question

我有以下问题：

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

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

可能没有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倍数

Answer 1

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

但是，通过在计算值中寻找重复周期，可以做得更好。最简单的方法是存储repdigit的每个连续值。如果一个值出现两次，则表示您已经进入了一个重复周期，并且没有解决方案。但是没有必要存储repdigit的每个值。循环的每次迭代相当于计算a=10、c=d和m=n的linear congruential generator的下一个输出。如果初始值为零，则输出序列将在最多3次迭代后进入重复循环

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

例如，当n和d是互质且n是3的幂时，这个LCG将产生一个maximal length sequence，在这种情况下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