使得 X % P == N 的最小数字 X 是多少？其中涉及到IT技术。

Question

这��问题来自ACM-ICPC罗马尼亚档案馆。给定T组(N, P)，找到每组元组的最小X，使得X%P == N。如果不可能，输出-1。X只能由数字集{2、3、5、7}中的数字构成。

例如：

3

52 100

11 100

51 1123

给定示例的输出：

52

-1

322352

限制条件：

1 ≤ P ≤ 5 * 10^6

1 ≤ N ≤ P - 1

我尝试使用递归函数解决此问题，该函数将使用给定集合中的数字构建数字并检查是否满足条件，但是这太慢了，因为我不知道何时停止搜索（即当给定元组没有解时）。作者提示以某种方式使用BFS，但我真的看不出如何使用该问题的输入数据构造有意义的图形。

你会如何解决这个问题？

- user43389

---

我不想寻找任何形式的争论，我已经阅读了很多基于与我帖子中使用的类似概念的问题。SO建议10个相关问题，涉及相同的问题解决范式。这是一个编程问题。 - user43389

@JamesKPolk - 我认为这个问题是合适的，因为OP正在寻求计算帮助。 - MyStackRunnethOver

由于这是模算术，您可以创建一个简单的循环并检查该值是否仅由允许的数字组成。它将非常快，因为您不需要测试每个可能的数字，只需测试一些即可。在最后一种情况下小于5000。我仍然会留下具体细节需要解决。 - Sami Kuhmonen

抱歉，我误将P的限制看作X的限制，因此结束位置并不像我想象的那么简单。必须仔细思考一下它是什么... - Sami Kuhmonen

@maraca 但是在什么时候您决定X变得太大或者没有解决方案了呢？毕竟，这似乎是最大的问题。 - user43389

Answer 1

您可以使用BFS解决此问题，从0开始，在该过程中，与数字n相邻的顶点为10n+2、10n+3、10n+5和10n+7。通过记录所有模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

- Paul Hankin