Sukarna_Paul's blog

By Sukarna_Paul, history, 9 months ago, In English,

How can I approach for this number theory problem ? [Problem Link](http:// https://codeforces.com/contest/1070/problem/A)

A. Find a Number time limit per test3 seconds memory limit per test256 megabytes inputstandard input outputstandard output

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 input 13 50 output 699998

input 61 2 output 1000000000000000000000000000001

input 15 50 output -1

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's a DP + BFS problem. Represent dp[i][j] as minimal digits required to build the number if our current sum is i and MOD d is j. Calculate this by BFS, then greedily pick the smallest number possible.