1950D.md (1507B)
1 Source: https://codeforces.com/problemset/problem/1950/D 2 3 D. Product of Binary Decimals 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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. 24 25 Input 26 27 The first line contains a single integer $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases. 28 29 The only line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$). 30 31 Output 32 33 For each test case, output "YES" (without quotes) if $n$ can be represented as a product of binary decimals, and "NO" (without quotes) otherwise. 34 35 You can output "YES" and "NO" in any case (for example, strings "yES", "yes", and "Yes" will be recognized as a positive response). 36 37 Example 38 39 Input 40 41 ``` 42 11 43 44 121 45 46 1 47 48 14641 49 50 12221 51 52 10110 53 54 100000 55 56 99 57 58 112 59 60 2024 61 62 12421 63 64 1001 65 ``` 66 67 Output 68 69 ``` 70 YES 71 YES 72 YES 73 YES 74 YES 75 YES 76 NO 77 NO 78 NO 79 NO 80 YES 81 ``` 82 83 Note 84 85 The first five test cases can be represented as a product of binary decimals as follows: 86 87 * $121 = 11 \times 11$. 88 * $1 = 1$ is already a binary decimal. 89 * $14\,641 = 11 \times 11 \times 11 \times 11$. 90 * $12\,221 = 11 \times 11 \times 101$. 91 * $10\,110 = 10\,110$ is already a binary decimal.