Repeating a Number
Time limit2sMemory limit128 MB
Find the minimum number of times a number N must be concatenated with itself so the resulting number is divisible by K, or report -1.
- Level
Medium5 of 10
- Topics
- Math, Number theory, Simulation
- Solved
- No attempts yet
Problem
You are given two positive integers, N and K.
Treat N as a decimal string and build a new number by writing the same string repeatedly. For example, if N = 10, writing it once gives 10, writing it twice gives 1010, and writing it three times gives 101010.
Find the minimum number of times N must be written so that the resulting number is divisible by K. If no such number of repetitions exists, output -1.
Input
The first line contains two positive integers N and K separated by a space. N is at most 1,000,000,000, and K is at most 100,000.
Output
Output the minimum number of times N must be written so that the resulting number is divisible by K. If it is impossible, output -1.