Минимальное положительное целое число n, которое делится на d и имеет сумму цифр, равную s - PullRequest
Новая
       16

Минимальное положительное целое число n, которое делится на d и имеет сумму цифр, равную s

0 голосов
/ 06 ноября 2018

Я нашел эту проблему на 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, то текущий путь не стоит искать. Но что является основанием для сброса пути, если мы ранее встречали число с тем же остатком и суммой цифр?

Один из примеров: д = 13 с = 50

Когда путь достигает 120, это вызывает условие, потому что мы уже видели число 3, которое имеет тот же остаток, что и 120, и ту же сумму цифр.

1 Ответ

0 голосов
/ 06 ноября 2018

Используя ваш пример 120 и 3 и немного модульной арифметики , довольно легко показать, почему 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 эквивалентны в том, что касается проблемы, и первые могут быть отброшены.

...