Problem Link: https://dmoj.ca/problem/pdigit

This post will dicuss the solution for the problem linked above, that I created for a mini-contest in DMOJ.

Statement

You are given two integers ~n~ and ~k~, and can perform operations to ~n~.

Each operation allows you to prepend a digit ~d~ ~(0 \le 0 \le 9)~ to ~n~, and it is your task to determine if there exists a sequence of operations such that ~n~ will end up being divisible by ~k~.

Note: ~n~ and ~k~ can be fairly large with bounds ~(1 \le n, k \le 10^9)~, and you are required to answer ~t~ test cases.

Subtask 1

~1 \le k, \le 9~

Since divisibility rules exist from ~1~ to ~9~, we can use logic to solve for each case.

Note: This subtask doesn’t exist in the linked problem.

Subtask 2

~1 \le t \le 10^5~

~1 \le n, k, \le 10^9~

Step 1

Since ~t~ can be ~10^5~, we are looking for a ~\mathcal{O}(T \cdot \log N)~, or ~\mathcal{O}(T)~ with some form of log factor, unless this problem can be solved in constant time.

Next, notice that the integer ~n~, after say ~m~ operations, can also be represented with an equation. Suppose ~d_1, d_2, d_3, \dots, d_m~ are the digits prepended to ~n~ in order from ~1~ to ~m~.

All the operations can be represented as the addition of one integer with digits ~d_1, d_2, d_3, \dots, d_m~ to the front of ~n~.

So, let ~y~ be the integer with digits ~d_1, d_2, d_3, \dots, d_m~.

Example: Prepend The Integer 23 to 45:

Our resultant value will have a length of ~2 + 2 = 4~, and we can picture this operation to be ~2300 + 45 = 2345~.

Hence notice, that we create ~0~s in the position where the ~45~ will go into. The number ~2300~ is created by multiplying ~23 \cdot 10^2~.

Generalization: Add Integer ~y~ to ~n~:

Define the length of an integer to be ~\text{len}(x)~. For example, ~\text{len}(342) = 3~.

The new integer ~n~, with ~y~ prepended is:

\[10^{\text{len}(n)} \cdot y + n\]

Step 2

How do we represent that a number ~n~ is divisible by ~k~ with an equation? We can write this as ~n \equiv 0 \pmod k~, where ~n~ is congruent to ~0 \pmod k~.

Since we figured out how to represent the final value of ~n~, our congruence is:

\[10^{\text{len}(n)} \cdot y + n \equiv 0 \pmod k\]

Our linear congruence is similar to form of ~ax \equiv b \pmod m~, where ~a = 10^{\text{len}(n)} \cdot y~, ~b = -n~ and ~m = k~.

Since the problem asks us YES or NO, does a sequence of operations exist, this is similar to asking if the congruence has any solution.

A congruence of the form ~ax \equiv b \pmod m~, has a solution when ~\text{gcd}(a, m)~ is a divisor of ~b~.

Therefore we output YES when ~\gcd(10^{\text{len}(n)}, k)~ is a divisor of ~-n \bmod k~, and NO otherwise.