ShareOJ Programming Contest vol.1 B - One Digit Factorization
- サイト
- ShareOJ
- コンテスト
- ShareOJ Programming Contest vol.1
- 問題
- B - One Digit Factorization(常設版)
正整数 が、 桁の正整数だけの積で表せるかを判定する問題です。テストケースは 個あり、、 です。
素因数で言い換える
Section titled “素因数で言い換える”が 桁の正整数だけの積で表せることは、 の素因数が だけであることと同じです。
- 桁の正整数 は、どれも素因数が だけです。そのため、これらの積の素因数も だけです。
- 逆に、素因数が だけなら、 を素因数分解した式がそのまま 桁の正整数の積になっています。 のときも、 自体が 桁なので表せます。
割れるだけ割る
Section titled “割れるだけ割る” を でそれぞれ割り切れなくなるまで割り、最後に が残れば Yes、そうでなければ No です。
1 回割るたびに は半分以下になるので、割る回数は 回ほどで済みます。
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")