結果
問題 | No.1396 Giri |
ユーザー |
![]() |
提出日時 | 2021-02-14 21:47:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 591 ms / 2,000 ms |
コード長 | 921 bytes |
コンパイル時間 | 341 ms |
コンパイル使用メモリ | 82,368 KB |
実行使用メモリ | 100,168 KB |
最終ジャッジ日時 | 2024-07-22 09:18:45 |
合計ジャッジ時間 | 6,836 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
mod = 998244353 n = int(input()) erathosthenes = [1] * (n + 1) for i in range(2, len(erathosthenes)): if erathosthenes[i] == 1: for j in range(i, len(erathosthenes), i): if erathosthenes[j] == 1: erathosthenes[j] = i for i in reversed(range(1, len(erathosthenes))): if erathosthenes[i] == i: max_prime = i break factors = {} for i in range(1, len(erathosthenes)): if i != max_prime: current = i primes = {} while erathosthenes[current] > 1: p = erathosthenes[current] count = primes.get(p, 0) primes[p] = count + 1 current //= p for p, count in primes.items(): c = factors.get(p, 0) factors[p] = max(c, count) result = 1 for p, count in factors.items(): for _ in range(count): result *= p result %= mod print(result)