No.1730 GCD on Blackboard in yukicoder
とりゐ
るさ問題文最終更新日: 2021-10-23 11:16:13
問題文
以下の問題を，各 $K=0,1,\ldots,N-1$ に対して解いてください．元ネタ ABC125-C (GCD on Blackboard)$N$ 個の整数 $A_1, A_2, \ldots, A_N$ が黒板に書かれています．
あなたはこの中から整数をちょうど $K$ 個選んで，それぞれ $1$ 以上 $10^6$ 以下の好きな整数に書き換えます．
元の整数と同じ整数に書き換えても構いません．
書き換えた後の $N$ 個の整数の最大公約数の最大値を求めてください．
入力
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。