結果

問題 No.811 約数の個数の最大化
ユーザー tktk_snsntktk_snsn
提出日時 2021-04-28 18:34:46
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,523 bytes
コンパイル時間 87 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 16,772 KB
最終ジャッジ日時 2024-07-07 17:00:24
合計ジャッジ時間 1,498 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
16,052 KB
testcase_01 AC 34 ms
16,028 KB
testcase_02 AC 60 ms
16,608 KB
testcase_03 AC 39 ms
16,020 KB
testcase_04 AC 36 ms
16,020 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 38 ms
16,092 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 61 ms
16,644 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
from collections import Counter
from itertools import chain


def prime_sieve(N):
    #sieve[i] : iの最小の素因数
    sieve = [0] * (N + 1)
    prime = []
    for i in range(2, N + 1):
        if sieve[i] == 0:
            sieve[i] = i
            prime.append(i)
        for p in prime:
            if p > sieve[i] or i * p > N:
                break
            sieve[i * p] = p
    return sieve


def prime_set(N):
    """
    Nまでの素数のsetを返す
    """
    if N < 4:
        return ({}, {}, {2}, {2, 3})[N]
    Nsq = int(N ** 0.5 + 0.5) + 1
    primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
    for i in range(5, Nsq, 2):
        if i in primes:
            primes -= set(range(i * i, N + 1, i * 2))
    return sorted(primes)


def get_primefactor(N):
    sieve = prime_sieve(N+10)
    pf = []
    while sieve[N]:
        pf.append(sieve[N])
        N, m = divmod(N, sieve[N])
    return pf


N, K = map(int, input().split())
cnt = Counter(get_primefactor(N))

# まずはK個素因数を割り当て
ans = 1
get = defaultdict(int)
while K:
    for key in sorted(cnt.keys()):
        if cnt[key]:
            ans *= key
            cnt[key] -= 1
            get[key] += 1
            K -= 1
        if not K:
            break

primes = prime_set(10**5+1)
for P in range(1, 20):
    for pr in primes:
        if ans * pr >= N:
            break
        if get[pr] >= P:
            continue
        get[pr] += 1
        ans *= pr
print(ans)
0