Tóm tắt:

Link gốc 1950D

Cho số nguyên dương N, xác định xem N có phân tích được thành tích các số giả nhị phân hay không?
Số giả nhị phân là số nguyên khi biểu diễn trong hệ thập phân chỉ chứa các chữ số 0, 1.

Input:

• Dòng đầu ghi số nguyên T là số lượng test
• Dòng tiếp theo ghi các số nguyên N tương ứng cần kiểm tra.

Output:

• Tương ứng mỗi test ghi ra trên một dòng:
  • Yes: Nếu số đã cho có thể phân tích được thành dạng yêu cầu
  • No trong trường hợp ngược lại.

Gợi ý:

Phương án 1:

Sử dụng đệ quy:
Nếu N đã là số giả nhị phân –> return True.
Tìm ước nhỏ nhất của N là số giả nhị phân (x) ==> gọi đệ quy kiểm tra giá trị (N/x)
Nếu không tìm được ước thỏa mãn –> return False

Phương án 2:

Sử dụng mảng hằng chứa các số nguyên là số giả nhị phân trong khoảng từ $[1,10^5]$
Với số nguyên N cần kiểm tra, check tất cả các ước có nằm trong mảng hằng hay không.