結果

問題 No.811 約数の個数の最大化
コンテスト
ユーザー ntuda
提出日時 2025-04-08 21:42:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 76 ms / 2,000 ms
コード長 814 bytes
コンパイル時間 454 ms
コンパイル使用メモリ 82,108 KB
実行使用メモリ 68,672 KB
最終ジャッジ日時 2025-04-08 21:42:21
合計ジャッジ時間 2,436 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import gcd

N, K = map(int, input().split())

# エラストネスの篩応用　素因数の数
P = [0] * (N + 1)
P[0] = 0
for i in range(2, N):
    if P[i] == 0:
        for j in range(i, N + 1, i):
            P[j] += 1
        tmp = i * i
        while tmp <= N:
            for j in range(tmp, N + 1, tmp):
                P[j] += 1
            tmp *= i

# エラストネスの篩応用　約数の数
Q = [2] * (N + 1)
Q[0] = 0
Q[1] = 0
for i in range(2, N):
    if i * i > N:
        break
    for j in range(2 * i, N + 1, i):
        if i * i > j:
            continue
        if i * i == j:
            Q[j] += 1
        else:
            Q[j] += 2

ndiv = 0
ans = 0
for i in range(1, N):
    if P[gcd(i, N)] >= K:
        if ndiv < Q[i]:
            ndiv = Q[i]
            ans = i
print(ans)
0