No.1730 GCD on Blackboard in yukicoder

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1730 GCD on Blackboard in yukicoder

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 117
作問者 :

とりゐ / テスター :

るさ

10 ProblemId : 6893 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2021-10-23 11:16:13

問題文

以下の問題を，各

K = 0, 1, \dots, N - 1

に対して解いてください．

$N$ 個の整数 $A_{1}, A_{2}, \dots, A_{N}$ が黒板に書かれています．

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

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

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

元ネタ ABC125-C (GCD on Blackboard)

入力

 $N$ 
 $A_{1} A_{2} \dots 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もしくは右上の雲マークをクリックしてアカウントを作成してください。