結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
![]() |
提出日時 | 2024-03-12 11:56:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 397 ms / 2,000 ms |
コード長 | 1,200 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 82,712 KB |
実行使用メモリ | 78,208 KB |
最終ジャッジ日時 | 2024-09-29 22:15:13 |
合計ジャッジ時間 | 3,630 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
# Nを素因数分解して、約数の個数を最大化するには、より多くの素因数を使うのがいい、それで余れば2周目?# N400のとき、5を1個よりも2を2個選んだ方がいいということはあるか? それでは約数の個数を最大化できない# Nが小さいのでNまでの数を全探索するのがいいfrom collections import defaultdict# 辞書型に改造def 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] = 1if arr==[]:arr[n] = 1return arrN, K = map(int, input().split())N_factors = factorization(N)#print(N_factors)ans = 1mx = 0for n in range(1, N):n_factors = factorization(n)common = 0for p in n_factors:calc = min(n_factors[p], N_factors[p])common += calcif common >= K:count = 1for p in n_factors:count *= (n_factors[p]+1)if count > mx:mx = countans = nprint(ans)