結果

問題 No.1396 Giri
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:57:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,615 ms / 2,000 ms
コード長 3,200 bytes
コンパイル時間 234 ms
コンパイル使用メモリ 82,880 KB
実行使用メモリ 272,572 KB
最終ジャッジ日時 2025-03-26 15:59:03
合計ジャッジ時間 15,300 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from collections import defaultdict

MOD = 998244353

def main():
    N = int(sys.stdin.readline())
    if N == 1:
        print(1)
        return

    # Sieve of Eratosthenes to find smallest prime factors
    lpf = list(range(N + 1))
    for i in range(2, int(math.isqrt(N)) + 1):
        if lpf[i] == i:
            for j in range(i*i, N+1, i):
                if lpf[j] == j:
                    lpf[j] = i

    # Factorize each number and collect prime exponents
    prime_exp = defaultdict(list)
    max_exp = {}
    next_max = {}
    count_max = {}

    for i in range(2, N+1):
        x = i
        factors = defaultdict(int)
        while x > 1:
            p = lpf[x]
            factors[p] += 1
            x //= p
        for p, e in factors.items():
            prime_exp[p].append(e)

    # Determine max_exp, next_max, count_max for each prime
    for p in prime_exp:
        exp_list = prime_exp[p]
        unique_exps = sorted(list(set(exp_list)), reverse=True)
        max_e = unique_exps[0]
        max_exp[p] = max_e
        count_max[p] = exp_list.count(max_e)
        if len(unique_exps) >= 2:
            next_max[p] = unique_exps[1]
        else:
            next_max[p] = 0

    # Compute log_L for the overall LCM
    log_L = 0.0
    for p in max_exp:
        log_L += max_exp[p] * math.log(p)

    # Find the i with the minimum log after removal
    min_log = float('inf')
    best_i = 1  # default to i=1

    for i in range(1, N+1):
        current_log = log_L
        if i != 1:
            # Factorize i
            x = i
            factors = defaultdict(int)
            while x > 1:
                p = lpf[x]
                factors[p] += 1
                x //= p
            # Check each prime factor of i
            for p, e in factors.items():
                if p not in max_exp:
                    continue
                if e == max_exp[p]:
                    if count_max[p] == 1:
                        delta_e = max_exp[p] - next_max.get(p, 0)
                        current_log -= delta_e * math.log(p)
        # Update minimum
        if current_log < min_log:
            min_log = current_log
            best_i = i

    # Compute the LCM mod MOD for the best_i
    # First compute the overall LCM mod MOD
    lcm_mod = 1
    for p in max_exp:
        lcm_mod = lcm_mod * pow(p, max_exp[p], MOD) % MOD

    if best_i == 1:
        print(lcm_mod % MOD)
        return

    # Factorize best_i
    x = best_i
    factors = defaultdict(int)
    while x > 1:
        p = lpf[x]
        factors[p] += 1
        x //= p

    # Adjust the LCM mod MOD by removing best_i's contribution
    res = lcm_mod
    for p in factors:
        if p not in max_exp:
            continue
        e_i = factors[p]
        if e_i == max_exp[p] and count_max[p] == 1:
            # Remove p^max_exp and multiply p^next_max
            exponent_remove = max_exp[p]
            exponent_add = next_max.get(p, 0)
            inv = pow(p, exponent_remove, MOD)
            inv = pow(inv, MOD-2, MOD)
            res = res * inv % MOD
            res = res * pow(p, exponent_add, MOD) % MOD

    print(res % MOD)

if __name__ == "__main__":
    main()
0