algorithm - 满足 X % P == N 的最小数量 X

Question

这个问题取自 ACM-ICPC 罗马尼亚语文件。

You are given T tuples of the form (N, P), find the smallest number X for every tuple such that X % P == N. If this is not possible, print -1. X can only be formed using digits from the set {2, 3, 5, 7}.

示例:

3

52 100

11100

51 1123

给定示例的输出:

52

-1

322352

限制:

1 ≤ P ≤ 5 * 10^6

1 ≤ N ≤ P - 1

我试图通过使用递归函数来解决这个问题，该函数将使用给定集合中的数字构建数字并检查是否满足条件，但这太慢了，因为我不知道何时停止搜索(即何时有没有给定元组的解决方案)。

作者暗示以某种方式使用 BFS，但我真的没有看到任何方法可以使用此问题的输入数据构建有意义的图。

您将如何解决这个问题？

Answer 1

您可以使用 BFS 解决此问题，从 0 开始，其中与数字 n 相邻的顶点是 10n+2、10n+3、10n+5 和 10n+7。通过记录所有已排队的 mod p 数，可以减小搜索空间的大小，但更重要的是知道何时搜索了整个空间。

这是一个简单的 Python 实现:

import collections

def ns(n, p):
    q = collections.deque([0])
    done = set()
    while q:
        x = q.popleft()
        for d in [2, 3, 5, 7]:
            nn = 10 * x + d
            if nn % p in done:
                continue
            if nn % p == n:
                return nn
            q.append(nn)
            done.add(nn % p)
    return -1

assert ns(52, 100) == 52
assert ns(11, 100) == -1
assert ns(51, 1123) == 322352
assert ns(0, 55) == 55