結果
問題 |
No.811 約数の個数の最大化
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:47:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 139 ms / 2,000 ms |
コード長 | 1,524 bytes |
コンパイル時間 | 243 ms |
コンパイル使用メモリ | 83,072 KB |
実行使用メモリ | 78,464 KB |
最終ジャッジ日時 | 2025-03-31 17:48:23 |
合計ジャッジ時間 | 2,509 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
import sys import math from collections import defaultdict def sieve(n): spf = list(range(n + 1)) for i in range(2, int(math.isqrt(n)) + 1): if spf[i] == i: # i is a prime for j in range(i*i, n + 1, i): if spf[j] == j: spf[j] = i return spf def factorize(n, spf): factors = defaultdict(int) while n > 1: p = spf[n] factors[p] += 1 n = n // p while n % p == 0: factors[p] += 1 n = n // p return factors def main(): input_line = sys.stdin.readline().strip() N, K = map(int, input_line.split()) # Build SPF table up to N spf = sieve(N) # Factorize N to get its prime factors and their exponents n_factors = factorize(N, spf) max_div_count = -1 result = N # Initialize with a value larger than possible M for M in range(1, N): m_factors = factorize(M, spf) shared = 0 for p in m_factors: if p in n_factors: shared += min(m_factors[p], n_factors[p]) if shared >= K: div_count = 1 for e in m_factors.values(): div_count *= (e + 1) # Update the result if current M has more divisors or same but smaller if div_count > max_div_count or (div_count == max_div_count and M < result): max_div_count = div_count result = M print(result) if __name__ == "__main__": main()