Product of Binary Decimals
Contest: Codeforces Round 937 (Div. 4)
Difficulty rating: 1100
Tags: brute force, dp, implementation, number theory

Let's call a number a binary decimal if it is a positive integer and all digits in its decimal notation are either $$$0$$$ or $$$1$$$. For example, $$$1\,010\,111$$$ is a binary decimal, while $$$10\,201$$$ and $$$787\,788$$$ are not.

Given a number $$$n$$$, you are asked whether or not it is possible to represent $$$n$$$ as a product of some (not necessarily distinct) binary decimals.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — the number of test cases.

The only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

Output format:
For each test case, output "YES" (without quotes) if $$$n$$$ can be represented as a product of binary decimals, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes", and "Yes" will be recognized as a positive response).

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
The first five test cases can be represented as a product of binary decimals as follows:

- $$$121 = 11 \times 11$$$.
- $$$1 = 1$$$ is already a binary decimal.
- $$$14\,641 = 11 \times 11 \times 11 \times 11$$$.
- $$$12\,221 = 11 \times 11 \times 101$$$.
- $$$10\,110 = 10\,110$$$ is already a binary decimal.

Example input:
11
121
1
14641
12221
10110
100000
99
112
2024
12421
1001

Example output:
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
YES

Editorial:
First, let's make precompute list of all binary decimals at most $$$10^5$$$. You can do it in many ways, for example iterating through all numbers up to $$$10^5$$$ and checking if each is a binary decimal.
Let's call a number good if it can be represented as the product of binary decimals. For each test case, we will write a simple recursive function. $$$n$$$ is good if:
• $$$n=1$$$, or
• $$$\frac{n}{i}$$$ is good, for some binary decimal $$$i>1$$$.
Even if your implementation is slightly too slow, there are not many good numbers; you can simply precompute them all locally and hardcode them to get a solution that works in $$$\mathcal{O}(1)$$$. $$$\phantom{\text{Here is a long string of text so that there is a horizontal line separating sections.}}$$$ For the curious: we will compute an upper bound on the complexity, given by the (rather loose) recurrence $$$$$$T(n) \leq 2 T\left(\left\lfloor\frac{n}{10}\right\rfloor\right) + 4 T\left(\left\lfloor\frac{n}{100}\right\rfloor\right) + 26 T\left(\left\lfloor\frac{n}{1000}\right\rfloor\right).$$$$$$ By the Akra-Bazzi method, $$$$$$T(n) \in \mathcal{O}(n^{\log_{10} \alpha}) = \mathcal{O}\left(n^{\log_{10} \left( \frac{2 + \sqrt[3]{395 - 3\sqrt{16881}} + \sqrt[3]{395 + 3\sqrt{16881}}}{3} \right)}\right) \approx \mathcal{O}(n^{0.635})\,,$$$$$$ where $$$\alpha$$$ is the (unique) real number satisfying $$$\alpha^3 = 2 \alpha^2 + 4 \alpha + 26$$$. This is probably fast enough, and this is still a very large overestimate.
A more accurate estimate can be made by picking the solution to $$$\alpha^5 = 2\alpha^4 + 4\alpha^3 + 8\alpha^2 + 16\alpha+2$$$, which gives a bound $$$\mathcal{O}(n^{0.587})$$$.