結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
![]() |
提出日時 | 2023-03-09 11:21:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 500 ms / 2,000 ms |
コード長 | 1,083 bytes |
コンパイル時間 | 321 ms |
コンパイル使用メモリ | 82,600 KB |
実行使用メモリ | 82,816 KB |
最終ジャッジ日時 | 2024-09-18 02:50:06 |
合計ジャッジ時間 | 4,199 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
# 難しく考えすぎたらしい # 全探索すればいい # N<10**5と小さい # 素因数分解はdefaultdict型に改造した # 辞書型に改造した from collections import defaultdict def factorization(n): arr = defaultdict(int) temp = n for i in range(2, int(-(-n**0.5//1))+1): if temp%i==0: cnt=0 while temp%i==0: cnt+=1 temp //= i arr[i] = cnt if temp!=1: arr[temp] = 1 #if arr==[]: #素因数として1が加えられないようにした # arr.append([n, 1]) return arr N, K = map(int, input().split()) N_factors = factorization(N) candidates = [] for i in range(1, N): i_factors = factorization(i) common = 0 for d in N_factors: common += min(N_factors[d], i_factors[d]) if common >= K: div_count = 1 for di in i_factors: div_count *= (i_factors[di]+1) candidates.append([div_count, i]) candidates.sort(key = lambda x:(-x[0], x[1])) print(candidates[0][1]) #print(candidates)