Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

I Am Good

By Zeronfinity · Limits 2s, 512 MB

I am trying to become a good guy, because it doesn't take money to become good. So here's a short and simple problem statement because I am a good guy! 🙂

Given two integers XX and PP, find the minimum positive value of KK such that f(X,K)f(X, K) is divisible by PP.

f(X,K)f(X, K) is defined as the KK-times concatenation of the integer XX (without leading zeroes).

For example,

  • f(123,3)=123123123f(123, 3) = 123123123
  • f(54,4)=54545454f(54, 4) = 54545454
  • f(123,2)=123123f(123, 2) = 123123
  • f(7,5)=77777f(7, 5) = 77777


Input will start an integer TT (1T101 \le T \le 10) denoting the number of test cases.

In each test case, two space separated integers XX (1X1041 \le X \le 10^4) and PP (1P10101 \le P \le 10^{10}) will be given.


For each test case, print the minimum positive value of KK in a single separate line.

If no such KK exists, print -1.


123 9
123 10

In the first test case, f(123,3)=123123123f(123, 3) = 123123123 is divisible by 9 while 123123 and 123 are not divisible by 9. Thus 3 is the minimum possible value of KK for this test case.

In the second test case, f(123,K)f(123, K) can never be divisible by 10 no matter what KK is.



19% Solution Ratio

EgorKulikovEarliest, Jan '20

YouKnowWhoFastest, 0.0s

EgorKulikovLightest, 131 kB

rebornShortest, 1076B


Login to submit


Let L be the length of X (number of digits). Then, f(X,K)=∑i=0K−110iLX=X∑i=0K−110iL=X10KL−110L−1f(X,...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.