最小数量X使得X%P == N.

Question

这个问题来自ACM-ICPC罗马尼亚档案.

你得到形式(N,P)的T元组,找到每个元组的最小数字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,但我真的没有看到使用此问题的输入数据构建有意义的图形的任何方法.

你会如何解决这个问题？

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