可被 d 整除且数字和等于 s 的最小正整数 n

Question

我在 codeforces (http://codeforces.com/problemset/problem/1070/A) 上发现了这个问题，我试图理解已发布的一个非常优雅的解决方案：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int d,s;

struct node
{
    int mod,sum;
    char s[700];
    int len;
};

queue<node> Q;
bool v[512][5200];

int main()
{
    scanf("%d%d",&d,&s);
    Q.push({0,0,0,0});
    while(!Q.empty())
    {
        node a=Q.front();Q.pop();
        for(int i=0;i<10;i++)
        {
            node b=a;
            b.s[b.len++]=i+'0';
            b.mod=(b.mod*10+i)%d;
            b.sum+=i;
            if(v[b.mod][b.sum] || b.sum>s) continue;
            v[b.mod][b.sum]=1;
            if(b.mod==0&&b.sum==s)
            {
                puts(b.s);
                return 0;
            }
            Q.push(b);
        }
    }
    puts("-1");
    return 0;
}

我知道树状搜索是通过在前缀中添加数字并将它们放入队列来完成的。搜索是这样的 1,2,3,4... 然后是 10, 11, 12... 20, 21, 22... 等等

我不明白的是以下停止条件：

if(v[b.mod][b.sum] || b.sum>s) continue;

很明显，如果位数之和大于s，则当前路径不值得追寻。但是如果我们之前遇到过余数和位数相同的数，那么丢弃路径的依据是什么？

一个例子是这样的： d = 13 s = 50

当路径到达120时触发条件，因为我们已经看到了数字3，它的余数与120相同，位数和也相同

Answer 1

使用你的 120 和 3 的例子以及一些 modular arithmetic，很容易证明，为什么 120 是基于 3 已经测试过的事实来排序的：

模运算中的加法和乘法定义为：

((a mod n) + (b mod n)) mod n = (a + b) mod n
((a mod n) * (b mod n)) mod n = (a * b) mod n

使用这些，我们可以证明对于任何额外的数字 x，余数模 d 将保持不变：

(120 * 10 + x) mod d = ((120 mod d) * (10 mod d) + (x mod d)) mod d
(  3 * 10 + x) mod d = ((  3 mod d) * (10 mod d) + (x mod d)) mod d

因为我们知道3 mod d = 120 mod d，我们知道如果我们用相同的附加数字测试上面两个项，它们将具有相同的余数。

但它们的数字之和也相等，这意味着可以将同一组新数字应用于两个数字。所以120和3在问题上是等价的，前者可以舍弃

可被 d 整除且数字和等于 s 的最小正整数 n

Minimal positive integer n which is divisible by d and has sum of digits equal to s

number-theory