Product of Binary Decimals (Codeforces 1950D)
Tags: Implement, 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: 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: 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).

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. 

Sample Inputs:
11
121
1
14641
12221
10110
100000
99
112
2024
12421
1001

Sample Outputs:
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
YES

Solution (Python):
import math
ans = ''
numCases = int(input())
temp = [int(format(x, 'b')) for x in range(2, 64)]
helper = set(temp)
for x in temp:
    for y in temp:
        z = y
        while len(str(z * x)) <= 6:
            z *= x
            helper.add(z)
helper.add(1)
for i in range(numCases):
    curr = int(input())
    if curr in helper:
        ans += 'YES'
    else:
        ans += 'NO'
    if i != numCases - 1:
        ans += '\n'
print(ans)

Solution (Python):
import sys
import io
import itertools
DEBUG = False

def input():
    if DEBUG:
        return buf.readline().strip()
    else:
        return sys.stdin.readline().strip()
nums = []
for i in range(1, 33):
    b = 0
    u = 1
    while i > 0:
        ld = i % 2
        b = b + ld * u
        i = i // 2
        u *= 10
    nums.append(b)
dp = set([1])
for n in nums[1:]:
    for d in list(dp):
        while d <= 100000:
            dp.add(d)
            d = d * n

def solve(n):
    if n in dp:
        print('YES')
    else:
        print('NO')

def main():
    testcases = int(input())
    for _ in range(testcases):
        n = int(input())
        solve(n)
if __name__ == '__main__':
    if DEBUG:
        buf = io.StringIO(test_in)
    main()

Solution (Python):
import math
import sys
import heapq
from collections import deque
from queue import Queue
from queue import PriorityQueue
sys.setrecursionlimit(1000000)
input = lambda : sys.stdin.readline().strip()
a = [1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111, 100000]
dq = deque()
f = {}
for i in a:
    dq.append(i)
m = 10 ** 5
while dq:
    j = dq.popleft()
    for i in a:
        t = j * i
        if t <= m:
            if f.get(t) == None:
                f[t] = 1
                dq.append(t)
        else:
            break
count = int(input())
for _ in range(count):
    n = int(input())
    if f.get(n):
        print('YES')
    else:
        print('NO')