結果

問題 No.1396 Giri
ユーザー NyaanNyaanNyaanNyaan
提出日時 2021-02-14 21:26:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,411 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 86,916 KB
実行使用メモリ 79,856 KB
最終ジャッジ日時 2023-09-29 14:30:37
合計ジャッジ時間 5,876 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 164 ms
79,508 KB
testcase_01 AC 167 ms
79,736 KB
testcase_02 WA -
testcase_03 AC 167 ms
79,668 KB
testcase_04 AC 166 ms
79,516 KB
testcase_05 WA -
testcase_06 AC 164 ms
79,452 KB
testcase_07 WA -
testcase_08 AC 166 ms
79,612 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
権限があれば一括ダウンロードができます

ソースコード

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