水以下コンテスト
コンテスト日時
2024/03/30 (Sa) 14:00 - 17:05

H - LCM and GCD

Ceylon
2
s
1024
MB
100

問題文

黒板に $N$ 個の正整数 $A_1, A_2, \ldots, A_N$ が書かれています。

あなたは以下の操作を行えなくなるまで繰り返します。

  • 黒板に書かれている数を $2$ つ選んで消す。消した数を $x, y$ として、
    「$x$と$y$の最大公約数」 と 「$x$と$y$の最小公倍数」を黒板に書き加える。
    • ただし、黒板に書かれている数の組み合わせが操作の前後で変化しないような操作は行うことができない。

操作を行えなくなるまで繰り返したのち、
黒板に書かれているすべての数字を昇順に並び替え、この数列を $B$ とします。(操作が有限回で終了することは証明できる。)

数列 $B$ の各要素の値は非常に大きくなることがあるので、各要素を $998244353$ で割ったあまりを求めてください。

制約

  • $2 \leq N \leq 10^5$
  • $1 \leq A_i \leq 2 \times 10^5~~(1 \leq i \leq N)$
  • 入力はすべて整数

部分点

以下の条件を満たすテストケースにすべて正解したとき、記載された点数が与えられる。

  1. (10点) $N = 2$
  2. (40点) $N \leq 1000,~ (A_1, A_2, \ldots, A_N)$ の最小公倍数 $\leq 10^{18}$
  3. (50点) 追加の制約なし

入力

入力は、以下の形式で標準入力から与えられる。

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

出力

数列 $B$ の各要素を $998244353$ で割ったあまりを空白区切りで出力せよ。

入力例 1
2 6 10
出力例 1
2 30
  • はじめ、 黒板に書かれている数は $(6, 10)$ です。
  • 6と10を選んで操作を行うと 黒板に書かれている数は $(2, 30)$ になります。
  • これ以上操作をすることができないため、$B = (2, 30)$ です。
  • このサンプルは部分点1の制約を満たします。
入力例 2
3 4 6 8
出力例 2
2 4 24
  • はじめ、 黒板に書かれている数は $(4, 6, 8)$ です。
  • まず、4と6を選んで操作を行うと 黒板に書かれている数は $(2, 12, 8)$ になります。
  • 次に、12と8を選んで操作を行うと 黒板に書かれている数は $(2, 4, 24)$ になります。
  • これ以上操作をすることができないため、$B = (2, 4, 24)$ です。
  • このサンプルは部分点2の制約を満たします。
入力例 3
4 161749 170324 185833 197173
出力例 3
1 1 49 633795587
  • 昇順に並び替えた後に $998244353$ で割った余りを計算し、出力してください。
  • このサンプルは部分点3の制約を満たします。
提出
C++23 (g++ 12.2.0)