Codeforces 1070A Find a Number(BFS) 2018-2019 ICPC, NEERC, Southern Subregional Contest Problem A

Description

You are given two positive integers d and s. Find minimal positive integer n which is divisible by d and has sum of digits equal to s.

Input

The first line contains two positive integers d and s$(1≤d≤500,1≤s≤5000)$ separated by space.

Output

Print the required number or -1 if it doesn’t exist.

---

Sample Input

Input

13 50

Output

699998

Input

61 2

Output

1000000000000000000000000000001

Input

15 50

Output -1

---

这道题是看了别人后的代码才写的，看到代码后没想到居然是个BFS（果然还是自己太菜啊） 就是让你求一个数，这个数能被$s$整除，且每位数相加$=d$。 看了别人ac的代码后发现其实很简单,运用同余定理就行了。。。。QAQ我怎么这么菜

---

思路 先根据位数进行BFS，如果$位数和>s$就不入队，剩下的每次入队前都$mod$ $d$就好了（控制数字大小别超$int$。然后当余数等于$0$（正好被$d$整除了），位数和等于$s$的时候就是答案

---

代码如下

#include <queue>
#include <map>
#include <unordered_map>
#include <queue>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <fstream>
#include <iostream>
#include <sstream>
#include <algorithm>
#define lowbit(a) (a&(-a))
#define _mid(a,b) ((a+b)/2)
#define _mem(a,b) memset(a,0,(b+3)<<2)
#define fori(a) for(int i=0;i<a;i++)
#define forj(a) for(int j=0;j<a;j++)
#define ifor(a) for(int i=1;i<=a;i++)
#define jfor(a) for(int j=1;j<=a;j++)
#define mem(a,b) memset(a,b,sizeof(a))
#define IN freopen("in.txt","r",stdin)
#define OUT freopen("out.txt","w",stdout)
#define IO do{\
    ios::sync_with_stdio(false);\
    cin.tie(0);\
    cout.tie(0);}while(0)
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define debug(a) cout <<(a) << endl
using namespace std;


struct node{
    int mod;
    int bit;
    string s;
    node(){};
    node(int m,int b,string ss){mod=m,bit=b,s=ss;}
};

bool v[501][5001];
string bfs(int d,int s){
    queue<node>q;
    q.push(node(0,0,""));
    v[0][0] = true;
    while(!q.empty()){
        node buf = q.front();
        q.pop();
        if(buf.bit <= s){
            if(buf.mod == 0&&buf.bit==s)
                return buf.s;
            fori(10){
                int bmod = (buf.mod*10+i)%d;
                int bbit = buf.bit+i;
                if(!v[bmod][bbit]){
                    v[bmod][bbit] = true;
                    q.push(node(bmod,bbit,buf.s+(char)(i+'0')));
                }
            }
        }
    }
    return "-1";
}
int main() {
    int s,d;
    cin >> d>> s;
    cout << bfs(d,s) << endl;
    return 0;

}