No.1529 Constant Lcm
タグ : / 解いたユーザー数 160
作問者 :
PCTprobability
/ テスター :
tatyam
Kazun
注意
この問題の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もしくは右上の雲マークをクリックしてアカウントを作成してください。