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

Question

I found this problem on codeforces (http://codeforces.com/problemset/problem/1070/A) and I'm trying to understand a pretty elegant solution that was posted:

#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;
}

I understand that a tree-like search is being done by adding digits to prefixes and putting them on a queue. The search goes like this 1,2,3,4... then 10, 11, 12... 20, 21, 22... etc.

What I don't understand is the following stop condition:

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

It is clear that if the sum of digits is greater than s, the current path is not worth pursuing. But what is the basis for discarding the path if we have previously encountered a number with the same remainder and sum of digits?

One example is this: d = 13 s = 50

When the path hits 120, it triggers the condition because we have already seen the number 3, which has the same remainder as 120, and the same sum of digits.

Answer 1

Using your example of 120 and 3 and a bit of modular arithmetic, it's fairly easy to show, why 120 is sorted out based on the fact that 3 was already tested:

Addition and multiplication in modular arithmetic are defined as:

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

Using these, we can show that for any additional digit x, the remainder modulo d will remain the same:

(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

since we know that 3 mod d = 120 mod d, we know that the two above terms will have the same remainder, if we test them with the same additional digit.

But their sum of digits is also equal, which means that the same set of new digits can be applied to both numbers. So 120 and 3 are equivalent as far as the problem is concerned and the former can be discarded.