結果
問題 | 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 defaultdictdef factorization(n):arr = defaultdict(int)temp = nfor i in range(2, int(-(-n**0.5//1))+1):if temp%i==0:cnt=0while temp%i==0:cnt+=1temp //= iarr[i] = cntif temp!=1:arr[temp] = 1#if arr==[]: #素因数として1が加えられないようにした# arr.append([n, 1])return arrN, K = map(int, input().split())N_factors = factorization(N)candidates = []for i in range(1, N):i_factors = factorization(i)common = 0for d in N_factors:common += min(N_factors[d], i_factors[d])if common >= K:div_count = 1for 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)