The Secret Number

Vadim starts with some positive integer $x$.

Then he appends a positive number of zeros to it. If he appends $k$ zeros, where $k \ge 1$, the new number is:

$y = x \cdot 10^k$

because appending one zero multiplies by $10$, appending two zeros multiplies by $100$, and so on.

The number he spreads is:

$n = x + y$

Substitute $y$:

$n = x + x\cdot 10^k$

Factor:

$n = x(10^k+1)$

So the whole problem collapses to this:

For some positive $k$, $10^k+1$ must divide $n$. Then the original secret number is:

$x = \frac{n}{10^k+1}$

That's it. No digit DP, no cursed string parsing, no wizard nonsense.

How many $k$ values matter?

Since $n \le 10^{18}$ and $x \ge 1$, we need:

$10^k+1 \le n$

So $k$ can only be from $1$ up to $17$ for this constraint. Trying all of them is completely fine.

For each $k$:

1. Compute $d = 10^k+1$.
2. If $n$ is divisible by $d$, then $x = n/d$ is valid.
3. Collect that $x$.

Output order

The statement wants all suitable $x$ in ascending order.

As $k$ gets larger, $10^k+1$ gets larger, so $x = n/(10^k+1)$ gets smaller. If we check $k=1,2,3,\dots$, we may find answers in descending order. Easiest fix: just sort the answers.

Example idea

For $n=1111$:

• $k=1$: $10^1+1=11$, and $1111/11=101$, valid.
• $k=2$: $10^2+1=101$, and $1111/101=11$, valid.

So the answers are $11$ and $101$.

Complexity

There are at most 18 divisor checks per test case.

$O(18 \log 18)$

per test case if we sort, which is just $O(1)$ in practice. The computer will not even notice.