### PROBLEM LINK:

**Author:** Balajiganapathi S

**Tester:** Jingbo Shang

**Editorialist:** Utkarsh Saxena

### PROBLEM

Given 2 integers A and M. Construct a set S of all integers that can be obtained by

deleting exactly one digit of A.

Find number of integers in S such that

concatenating zero or more integers from S to the right of it will give a multiple of M.

Constraints: 1 \le A \le 10^{10^6}, 1\leq M\leq 10^3

### EXPLANATION

Let the number of digits in A be D.

The number of elements in the set S will be D (repetitions are allowed).

Since the final aim is to make a number X such that X\equiv0\space mod\space M,

it is better to calculate each operation mod\space M.

\therefore Total number of distinct integers mod\space M in S can be atmost M.

We can find the integer mod\space M made by deleting i^{th} digit of A as

P_{i-1}*10^{N-i}*S_{i+1} mod\space M.

Here P_i = integer mod\space M represented by A[1..i],

S_i = integer mod\space M represented by A[i..N]

Denote S^\prime = The set of distinct integers mod\space M in S.

Assume we have concatenated some elements of S to form an integer \equiv X\space mod\space M.

Adding one more integer Y \in S to the right of X.

The new integer thus formed Z = X * 10^{N-1} + Y \space mod\space M.

Thus for a given remainder X we can convert it to another integer with remainder Z by the above formula.

We can make a graph of M vertices for these transitions.

The i^{th} node denotes that there exists a set of integers in S when concatenated together given i\space mod\space M.

There is a directed edge form node X to node Z if there exists a Y in S^\prime

such that Z = X * 10^{N-1} + Y \space mod\space M.

To answer the problem we need to find those nodes from which there is a path to node 0

and also are present in S^\prime.

This is equivalent to finding all those nodes that are reachable from 0 in the reverse

graph (direction of edges reversed).

### Time Complexity

Array P_i, Array S_i and Set S^\prime can be calculated in O(N)

Graph can be developed in O(M^2) time and space.

Finding all reachable nodes from 0 will take another O(M^2) time for bfs.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.