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$的时候就是答案
代码如下
1 |
|