結果

問題 No.1529 Constant Lcm
ユーザー ntuda
提出日時 2025-02-04 23:02:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,054 bytes
コンパイル時間 981 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 145,920 KB
最終ジャッジ日時 2025-02-04 23:03:17
合計ジャッジ時間 67,205 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 TLE * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

def seachPrimeNum(N):
    max = int(N ** 0.5)
    seachList = [i for i in range(2, N + 1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

def adic(dic, x):
    if x in dic:
        dic[x] += 1
    else:
        dic[x] = 1
    return

def factorization(x):
    dic = {}
    i = 0
    p = PL[i]
    while p * p <= x:
        if x % p == 0:
            adic(dic, p)
            x //= p
        else:
            i += 1
            if i < len(PL):
                p = PL[i]
    if x != 1:
        adic(dic, x)
    return dic

MOD = 998244353
from collections import defaultdict
dic = defaultdict(int)
N = int(input())
PL = seachPrimeNum(int(N ** 0.5) + 1000)
for i in range(1, N//2+1):
    X = factorization(i * (N - i))
    for k, v in X.items():
        if dic[k] < v:
            dic[k] = v
ans = 1
for k, v in dic.items():
    ans *= pow(k, v, MOD)
    ans %= MOD

print(ans)
0