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\le d\le 500,1\le s\le 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;}

转载于:https://www.cnblogs.com/bestsort/p/10588825.html

总结

以上是生活随笔为你收集整理的Codeforces 1070A Find a Number(BFS) 2018-2019 ICPC, NEERC, Southern Subregional Contest Problem A的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。