結果
問題 | No.811 約数の個数の最大化 |
ユーザー | FromBooska |
提出日時 | 2023-03-09 11:21:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 505 ms / 2,000 ms |
コード長 | 1,083 bytes |
コンパイル時間 | 198 ms |
コンパイル使用メモリ | 81,668 KB |
実行使用メモリ | 82,284 KB |
最終ジャッジ日時 | 2023-10-18 06:13:29 |
合計ジャッジ時間 | 5,238 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
55,724 KB |
testcase_01 | AC | 73 ms
71,080 KB |
testcase_02 | AC | 429 ms
76,884 KB |
testcase_03 | AC | 43 ms
55,724 KB |
testcase_04 | AC | 54 ms
61,972 KB |
testcase_05 | AC | 88 ms
76,544 KB |
testcase_06 | AC | 128 ms
76,884 KB |
testcase_07 | AC | 121 ms
76,804 KB |
testcase_08 | AC | 235 ms
76,840 KB |
testcase_09 | AC | 248 ms
77,372 KB |
testcase_10 | AC | 176 ms
76,756 KB |
testcase_11 | AC | 405 ms
77,128 KB |
testcase_12 | AC | 156 ms
76,780 KB |
testcase_13 | AC | 505 ms
82,284 KB |
testcase_14 | AC | 462 ms
77,068 KB |
ソースコード
# 難しく考えすぎたらしい # 全探索すればいい # 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)