Hi everyone,
This problem gives you two inputs N, M and N contains a number like (123) and all what you have to do is to add some digits on the left or the right of the (123) to make it divisible by M Hint about solving this problem, Or a solution for It?
constrains :- N<= 10^12 and M <= 2 * 10^5
Sample tests:-
(Test 1) 1 2 ===> 10 (Test 2) 2 11 ===> 22 (Test 3)234 823 ===> 12345
problem link: https://www.urionlinejudge.com.br/judge/en/problems/view/2788
And thanks In advance. :)
The first observation is that the answer is most definitely within the long long limit. That is because if $$$n' = n \times 10^6$$$, and $$$n^{\prime \prime} = n' + (m - n' \% m) \% m$$$ is a multiple of $$$m$$$. Another important observation that immediately follows from the above observation is that since to generate $$$n^{\prime \prime}$$$, we have to append 6 digits. Since appending 6 digits can generate a multiple of $$$m$$$, it doesn't make sense to check for any higher digit counts, and the number of digits in our answer lies within 6 + digit count of $$$n$$$.
Your answer is of the form $$$\mathrm{str}(s) + \mathrm{str}(n) + \mathrm{str}(t)$$$, where $$$+$$$ is string concatenation. By the way, once you have $$$n^{\prime \prime}$$$, you don't have to check for all $$$t$$$ of length six digits, because you can prove that $$$n^{\prime \prime}$$$ is the smallest of all those multiples of $$$m$$$ such that $$$t$$$ is of six digits. And of course, you don't need to check for $$$t$$$ with length greater than 6. So just brute force check over all $$$t$$$ of five digits or less. Oh, and given a particular $$$t$$$, how do you find the best $$$s$$$? If we denote $$$p = \mathrm{length}(\mathrm{str}(n)) + \mathrm{length}(\mathrm{str}(t))$$$, then $$$s$$$ is actually the smallest number so that $$$\left(10^p s\right) \% m = (m - (str(n) + str(t)) \% m) \% m$$$. (If $$$s$$$ turns out to be $$$0$$$, you can just leave the slot for $$$s$$$ empty.) How do you find such $$$s$$$ quickly? Simple — you precompute it for all remainders. $$$p \le 18$$$ and $$$s$$$ only needs to be varied from $$$0$$$ to $$$m - 1$$$ as we are working modulo $$$m$$$, so if such $$$s$$$ exists then it will be less than $$$m$$$. This precompute is thus in $$$O(18m)$$$ time.
Let me know if you need examples to understand the solution.
I will be grateful If you did so.
Okay, let's consider the sample testcase 234 823. The first solution n'' is 234000000 + (823 — 234000000 % 823) % 823. Btw, we're adding the second term to the original one to make it a multiple of $$$m$$$.
Let $$$\mathrm{dp}[i][j]$$$ denote the minimum $$$0 \le k \le m - 1$$$ so that $$$(10^i k) \% m = j$$$. If such a $$$k$$$ is not found, just assign -1 or INF to it. This dp table is computed by varying over all $$$0 \le k \le m - 1$$$ and assigning $$$dp[i][(10^i k) \% m] = min(k, dp[i][(10^i k) \% m]$$$.
Now we can check all cases where we have to append <= 5 digits to the end of 234. This can be done with a simple loop. Let's suppose that we append the number 5. This makes 2345, but we're not done yet. We have to concatenate the smallest to this number as a prefix to this so that it becomes a multiple of 823. But that number is simply $$$dp[4][(823 - 2345 \% 823) \% 823]$$$ because in the end we want a multiple of 823 (try to see why that is true). From our dp table, we will get this to be equal to 1, so one such answer is 12345. It turns out that if we vary over all $$$t$$$ (like 5 in this loop iteration) we will get 12345 as the minimum value required in the problem.
In implementation, be careful to also consider n'' in the answer, and make sure that you don't overflow long long if using C++. The function stoll is your friend, but don't use it whenever the string length is more than what is permitted in the long long datatype.