コンテンツにスキップ

ShareOJ Programming Contest vol.1 B - One Digit Factorization

サイト
ShareOJ
コンテスト
ShareOJ Programming Contest vol.1
問題
B - One Digit Factorization(常設版)

正整数 NN が、11 桁の正整数だけの積で表せるかを判定する問題です。テストケースは TT 個あり、1≤T≤1001 \le T \le 100、1≤N≤10181 \le N \le 10^{18} です。

NN が 11 桁の正整数だけの積で表せることは、NN の素因数が 2,3,5,72, 3, 5, 7 だけであることと同じです。

  • 11 桁の正整数 1,2,…,91, 2, \dots, 9 は、どれも素因数が 2,3,5,72, 3, 5, 7 だけです。そのため、これらの積の素因数も 2,3,5,72, 3, 5, 7 だけです。
  • 逆に、素因数が 2,3,5,72, 3, 5, 7 だけなら、NN を素因数分解した式がそのまま 11 桁の正整数の積になっています。N=1N = 1 のときも、11 自体が 11 桁なので表せます。

NN を 2,3,5,72, 3, 5, 7 でそれぞれ割り切れなくなるまで割り、最後に 11 が残れば Yes、そうでなければ No です。

1 回割るたびに NN は半分以下になるので、割る回数は log⁡21018<60\log_2 10^{18} < 60 回ほどで済みます。

Python
for _ in range(int(input())):
N = int(input())
for p in [2, 3, 5, 7]:
while N % p == 0:
N //= p
if N == 1:
print("Yes")
else:
print("No")