問題一覧 > 通常問題

No.1730 GCD on Blackboard in yukicoder

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 91
作問者 : とりゐとりゐ / テスター : るさるさ
6 ProblemId : 6893 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-23 11:16:13

問題文

以下の問題を,各 $K=0,1,\ldots,N-1$ に対して解いてください.

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

あなたはこの中から整数をちょうど $K$ 個選んで,それぞれ $1$ 以上 $10^6$ 以下の好きな整数に書き換えます.

元の整数と同じ整数に書き換えても構いません.

書き換えた後の $N$ 個の整数の最大公約数の最大値を求めてください.

元ネタ ABC125-C (GCD on Blackboard)

入力

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

  • $2\leq N\leq 2\times 10^5$
  • $1\leq A_i\leq 10^6$
  • 入力は全て整数である.

出力

$N$ 行にわたって出力してください.$i$ 行目には $K=i-1$ のときの答えを出力してください.

サンプル

サンプル1
入力
3
8 6 12
出力
2
6
12

  • $K=0$ のとき,何も書き換えません.$\gcd(8,6,12)=2$ です.
  • $K=1$ のとき,例えば $8$ を $12$ に書き換えると $\gcd(12,6,12)=6$ となり,これが最大です.
  • $K=2$ のとき,例えば $8$ を $36$ に,$6$ を $24$ に書き換えると $\gcd(36,24,12)=12$ となり,これが最大です.

サンプル2
入力
2
1000000 1000000
出力
1000000
1000000

元の整数と同じ整数に書き換えることも可能です.

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