問題一覧 > 通常問題

No.1529 Constant Lcm

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 129
作問者 : PCTprobabilityPCTprobability / テスター : tatyamtatyam KazunKazun
4 ProblemId : 6359 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-04 19:45:21

注意

この問題のTLは $3$ secです。

問題文

$\mathrm{lcm}(1\times (N-1),2 \times (N-2),3 \times (N-3),\dots, (N-2) \times 2, (N-1) \times 1) \bmod 998244353$ を求めてください。

厳密に述べると、正整数列 $A=(A_1,A_2,...,A_{N-1})$ を $A_i=i \times (N-i)$ で定めます。

$A$ の $N-1$ 要素全てで割り切れる最小の正整数を $998244353$ で割った余りを出力してください。

入力

$N$

  • 入力は全て整数である。
  • $2 \le N \le 10^6$

出力

$\mathrm{lcm}(1\times (N-1),2 \times (N-2),3 \times (N-3),\dots,(N-2) \times 2,(N-1) \times 1) \bmod 998244353$ を出力してください。

サンプル

サンプル1
入力
7
出力
60

$\mathrm{lcm}(1\times 6,2\times 5,3\times 4,4\times 3,5\times 2,6\times 1)=\mathrm{lcm}(6,10,12,12,10,6)=60$ なので、$60$ が解です。

サンプル2
入力
2021
出力
684169707

$998244353$ で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。