問題一覧 > 通常問題

No.1529 Constant Lcm

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 167
作問者 : PCTprobability / テスター : tatyam 👑 Kazun
お気に入りにしたユーザー ProblemId : 6359 / 自分の提出
問題文最終更新日: 2021-06-04 19:45:21
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 298 (順位表) の他の問題:

Note

The time limit for this problem is $3$ sec.

Problem Statement

Find $\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$.

Formally, define a sequence of positive integers $A=(A_1,A_2,...,A_{N-1})$ by $A_i=i \times (N-i)$.

Output the smallest positive integer divisible by all $N-1$ elements of $A$, modulo $998244353$.

Input

$N$

  • All inputs are integers.
  • $2 \le N \le 10^6$

Output

Output $\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$.

Sample

Sample 1
Input
7
Output
60

Since $\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$, the answer is $60$.

Sample 2
Input
2021
Output
684169707

Output the remainder when divided by $998244353$.

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