本文主要是介绍Codeforces Contest 1070 problem A Find a Number —— bfs求a的最小倍数且所有位的和是b，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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.
Examples
inputCopy
13 50
outputCopy
699998
inputCopy
61 2
outputCopy
1000000000000000000000000000001
inputCopy
15 50
outputCopy
-1
题意：
给你a和b，让你找出一个数使得这个数是a的倍数并且它所有位的和是b，且这个数最小。
题解：
我以前做过这道题目？好像是这样的，但是没什么印象了。而且我两次用的都是bfs！
因为它要你求得最小的数，那么我就觉得是bfs往下，这样求到的肯定是最小的，因为我是从小到大for的，dp不是dp，他只是一个类似vis的效果。我们记录两个状态：res：余数和sum：累加，如果之后有遇到过和之前一样的状态的话，那肯定是前面的优一点了，就算把dp全求出来，，也不过n*m的复杂度。输出由于我们是从高位往低位bfs的，那就dfs输出就好了。
如果从低位往高位bfs的话，余数的处理就会变得麻烦一点。。吧
#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
struct node
{int sum,num,res;node(){}node(int s,int n,int r):sum(s),num(n),res(r){}
}pre[505][5005];
void dfs(int x,int res)
{if(x==0&&res==0)return ;dfs(pre[res][x].sum,pre[res][x].res);printf("%d",pre[res][x].num);
}
int dp[505][5005];
int main()
{int n,m;scanf("%d%d",&n,&m);queue<node>Q;Q.push(node(0,0,0));dp[0][0]=1;int ans=-1;while(!Q.empty()){node v=Q.front();Q.pop();for(int i=0;i<=9;i++){if(i+v.sum>m)break;node ne;ne.res=(v.res*10+i)%n;ne.sum=v.sum+i;if(dp[ne.res][ne.sum])continue;pre[ne.res][ne.sum].res=v.res;pre[ne.res][ne.sum].sum=v.sum;pre[ne.res][ne.sum].num=i;dp[ne.res][ne.sum]=1;Q.push(node(ne.sum,i,ne.res));if(ne.sum==m&&ne.res==0){ans=m;break;}}if(ans!=-1)break;}if(ans==-1)return 0*printf("-1\n");dfs(ans,0);return 0;
}这篇关于Codeforces Contest 1070 problem A Find a Number —— bfs求a的最小倍数且所有位的和是b的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
