結果

問題 No.1396 Giri
コンテスト
ユーザー NyaanNyaan
提出日時 2021-02-14 21:26:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,411 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 82,472 KB
実行使用メモリ 78,304 KB
最終ジャッジ日時 2024-07-22 08:42:36
合計ジャッジ時間 4,884 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 4 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

def hcn_heapq(N): #N以下の高度合成数を列挙したリストを返す
    from heapq import heappop,heappush
    from math import log
    prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263]
    lim = [[2*int(log(p,q)) for q in prime] for p in prime] #枝刈り用配列
    # 初期状態
    q = [(2,2,[1])] # (n,nの約数の個数、nの指数表記)を保存する heapq
    res = [(1,1,[])]

    while q and q[0][0] <= N:
        n,val,lst = heappop(q)
        if val > res[-1][1]: #条件をみたすなら答に追加
            res.append((n,val,lst[:]))
        L = len(lst)
        e0 = lst[0]
        #全部１なら新しい素数で横に伸ばせる
        if e0 == 1: 
            heappush(q,(n*prime[L],val*2,[1]*(L+1)))
        #最上段の上を横方向に積む
        for i in range(L):
            if e0 > lst[i]: break #段差があると、もう伸ばせない
            if e0 >= lim[L][i]: break #枝刈り（重要）
            n *= prime[i]
            if n <= N:
                lst[i] += 1
                val = val//(e0+1)*(e0+2)
                heappush(q,(n,val,lst[:]))
    return res

N=int(input())
res = hcn_heapq(10**30)
for a,b,l in res:
  # print(a,b,l)
  if b>=N-1:
    print(a%998244353)
    exit(0)
0