問題一覧 > 通常問題

No.3717 GCD LCM GCD

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 36
作問者 : ぽえ / テスター : kazuppa 👑 loop0919
お気に入りにしたユーザー ProblemId : 13940 / 自分の提出
問題文最終更新日: 2026-09-18 21:21:47
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 514 (順位表) の他の問題:

Problem Statement

You are given positive integers $N,K$ and a sequence of positive integers $A=(A_1,A_2,\ldots,A_N)$ of length $N$.

For a permutation $P=(P_1,P_2,\ldots,P_N)$ of $1,2,\ldots,N$, define the integer $B(P)$ as

$B(P)=\mathop{\mathrm{lcm}}\limits_{1\le i\le N-K+1}\gcd(A_{P_i},A_{P_{i+1}},\ldots,A_{P_{i+K-1}})$

.

Find the greatest common divisor of $B(P)$ over all permutations $P$ of $1,2,\ldots,N$, modulo $998244353$.

Constraints

  • All input values are integers.
  • $2\le N\le 2\times 10^5$
  • $1\le K\le N$
  • $1\le A_i\le 10^6$ $(1 \le i \le N)$

Input

The input is given from Standard Input in the following format.

$N$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

Output the answer.

Sample

Sample 1
Input
4 2
2 4 6 9
Output
2

Sample 2
Input
5 5
12 18 30 42 66
Output
6

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