結果

問題 No.811 約数の個数の最大化
ユーザー 👑 KazunKazun
提出日時 2020-11-14 03:25:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 169 ms / 2,000 ms
コード長 1,074 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 86,912 KB
実行使用メモリ 78,724 KB
最終ジャッジ日時 2023-09-30 04:44:32
合計ジャッジ時間 3,248 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 73 ms
71,420 KB
testcase_01 AC 93 ms
76,668 KB
testcase_02 AC 164 ms
78,456 KB
testcase_03 AC 74 ms
71,484 KB
testcase_04 AC 81 ms
75,580 KB
testcase_05 AC 110 ms
77,564 KB
testcase_06 AC 115 ms
77,856 KB
testcase_07 AC 115 ms
77,748 KB
testcase_08 AC 137 ms
78,188 KB
testcase_09 AC 138 ms
77,896 KB
testcase_10 AC 132 ms
78,484 KB
testcase_11 AC 160 ms
78,136 KB
testcase_12 AC 124 ms
77,780 KB
testcase_13 AC 167 ms
78,572 KB
testcase_14 AC 169 ms
78,724 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def Smallest_Prime_Factor(N):
    """0,1,2,...,Nの最小の素因数のリスト(0,1については1にしている)
    """

    N=abs(N)
    L=[0]*(N+1)
    L[0]=L[1]=1

    for p in range(2,N+1):
        if L[p]==0:
            for q in range(p,N+1,p):
                if L[q]==0:
                    L[q]=p

    return L

def Faster_Prime_Factorization(N,L):
    """

    L:Smallest_Prime_Factors(N)で求めたリスト
    """
    N=abs(N)
    if N<=1:
        return [[N,1]]

    D=[]
    while N>1:
        a=L[N]
        k=0
        while L[N]==a:
            k+=1
            N//=a
        D.append([a,k])
    return D
#================================================
N,K=map(int,input().split())
T=Smallest_Prime_Factor(N)

A={p:e for p,e in Faster_Prime_Factorization(N,T)}

C=0
M=0
for i in range(2,N):
    B={p:e for p,e in Faster_Prime_Factorization(i,T)}

    X=0
    for p in B:
        if p in A:
            X+=min(A[p],B[p])

    if X>=K:
        D=1
        for p in B:
            D*=(B[p]+1)

        if D>C:
            C=D
            M=i
print(M)
0