結果

問題 No.1396 Giri
ユーザー lam6er
提出日時 2025-03-31 17:48:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 84 ms / 2,000 ms
コード長 1,399 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 82,944 KB
実行使用メモリ 80,384 KB
最終ジャッジ日時 2025-03-31 17:49:59
合計ジャッジ時間 2,871 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    mod_val = 998244353
    N = int(sys.stdin.readline().strip())
    
    if N == 1:
        print(1)
        return
    
    # Sieve of Eratosthenes to find primes up to N
    sieve = [True] * (N + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(N**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, N+1, i):
                sieve[j] = False
    primes = [i for i, is_prime in enumerate(sieve) if is_prime]
    
    candidates = []
    for p in primes:
        if p > N:
            continue
        # Find the maximum exponent e where p^e <= N
        e = 0
        current = 1
        while current * p <= N:
            current *= p
            e += 1
        # Check if p^e * 2 > N
        if current * 2 > N:
            candidates.append(p)
    
    # Compute X mod mod_val
    x_mod = 1
    for p in primes:
        # Find e_p again since we need to recompute (primes list is in order)
        e = 0
        current = 1
        while current * p <= N:
            current *= p
            e += 1
        # Compute p^e mod mod_val
        x_mod = x_mod * pow(p, e, mod_val) % mod_val
    
    if not candidates:
        print(x_mod)
        return
    else:
        p_max = max(candidates)
        inv_p = pow(p_max, mod_val - 2, mod_val)
        ans = x_mod * inv_p % mod_val
        print(ans)
    
if __name__ == '__main__':
    main()
0