結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
![]() |
提出日時 | 2024-12-28 10:23:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 300 ms / 2,000 ms |
コード長 | 985 bytes |
コンパイル時間 | 375 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 83,836 KB |
最終ジャッジ日時 | 2024-12-28 10:23:34 |
合計ジャッジ時間 | 3,631 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
from collections import defaultdict def seachPrimeNum(N): max = int(N**0.5) seachList = [i for i in range(2,N+1)] primeNum = [] while seachList[0] <= max: primeNum.append(seachList[0]) tmp = seachList[0] seachList = [i for i in seachList if i % tmp != 0] primeNum.extend(seachList) return primeNum def factorization(x): dic = defaultdict(int) for p in PL: if x in PL: dic[x] += 1 return dic while x % p == 0: dic[p] += 1 x //= p if x == 1: return dic N, K = map(int,input().split()) PL = seachPrimeNum(N) PL = set(PL) F1s = factorization(N) ans = 1 maxdiv = 1 for i in range(2,N): Fs = factorization(i) ndiv = 1 for v in Fs.values(): ndiv *= (v + 1) cnt = 0 for k,v in F1s.items(): cnt += min(Fs[k],v) if cnt < K: continue if ndiv > maxdiv: ans = i maxdiv = ndiv print(ans)