結果
問題 | No.1529 Constant Lcm |
ユーザー |
![]() |
提出日時 | 2021-06-05 08:56:12 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 666 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 140,344 KB |
最終ジャッジ日時 | 2024-11-21 04:11:55 |
合計ジャッジ時間 | 62,421 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 9 TLE * 15 |
ソースコード
from collections import Counter# 素因数分解(Counter)def prime_factorize(n):a = Counter()while n % 2 == 0:a[2] += 1n //= 2f = 3while f * f <= n:if n % f == 0:a[f] += 1n //= felse:f += 2if n != 1:a[n] += 1return an = int(input())MOD = 998244353# 始めに、1~nまでの素因数分解を前計算ps = [0] * (n + 1)for i in range(1, n + 1):ps[i] = prime_factorize(i)l = Counter()for i in range(1, n // 2 + 1):l |= (ps[i] + ps[n - i])ans = 1for k, v in l.items():ans *= pow(k, v, MOD)ans %= MODprint(ans)