結果
問題 | No.1611 Minimum Multiple with Double Divisors |
ユーザー |
![]() |
提出日時 | 2022-02-12 23:12:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,405 ms / 2,000 ms |
コード長 | 988 bytes |
コンパイル時間 | 178 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 78,208 KB |
最終ジャッジ日時 | 2024-06-29 02:26:46 |
合計ジャッジ時間 | 16,994 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
# https://yukicoder.me/problems/no/1611# No.1611 Minimum Multiple with Double Divisors# 素因数分解と約数の個数# X = (p1 ** m1) * (p2 ** m2) * ... * (pk ** mk)# と素因数分解されたとします. このとき, の正の約数の個数は# (m1 + 1)(m2 + 1)...(mk + 1) です.from collections import defaultdictdef prime_factorize(n):# 素因数分解 defaultdict# 2,3,5,7,11,13,17,19,23,29,31だけ見るa = defaultdict(int)for i in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:while n % i == 0:n //= ia[i] += 1return at = int(input())for _ in range(t):x = int(input())p = prime_factorize(x)cnt = 1for i in p.values():cnt *= (i + 1)for i in range(2, 32):ps = prime_factorize(i)dnt = cntfor k, v in ps.items():dnt = dnt // (p[k] + 1) * (p[k] + v + 1)if dnt == cnt * 2:print(i * x)break