codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.