結果

問題 No.811 約数の個数の最大化
ユーザー stngstng
提出日時 2022-07-06 16:09:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,780 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 65,244 KB
最終ジャッジ日時 2024-06-02 02:40:28
合計ジャッジ時間 1,455 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
53,108 KB
testcase_01 AC 37 ms
58,336 KB
testcase_02 AC 44 ms
63,628 KB
testcase_03 AC 34 ms
53,716 KB
testcase_04 AC 34 ms
52,664 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 43 ms
61,264 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 46 ms
63,868 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import bisect

def sieve_of_eratosthenes(n):
    prime = [True for i in range(n+1)]
    prime[0] = False
    prime[1] = False

    sqrt_n = math.ceil(math.sqrt(n))
    for i in range(2, sqrt_n):
        if prime[i]:
            for j in range(2*i, n+1, i):
                prime[j] = False

    return prime

# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor

n,k = map(int,input().split())

dic = {}
pr = prime(n)
for num, count in pr.items():
    if not num in dic.keys():
        dic[num] = count
    else:
        if dic[num] < count:
            dic[num] = count
#print(pr)
ans = 1
cnt = k
use = set()

li = sieve_of_eratosthenes(n)
ss = {}
for p in range(n+1):
    if li[p]:
        ss[p] = 0
        #ss.append(p)

while cnt > 0:
    for num,count in dic.items():
        if cnt == 0:
            break
        if count == 0:
            continue
        else:
            dic[num] -= 1
        ss[num] += 1
        cnt -= 1
        ans *= num
        use.add(num)

useli = [[] for i in range(21)]
addli = [[] for i in range(21)]

for num,count in ss.items():
    useli[count].append(num)

flag = False
for i in range(21):
    for j in useli[i]:
        if ans * j < n:
            ans *= j
            bisect.insort(useli[i+1],j)
            #addli[i+1].append(j)
        else:
            break

print(ans)
0