問題一覧 > 通常問題

No.1730 GCD on Blackboard in yukicoder

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 129
作問者 : とりゐ / テスター : るさ
お気に入りにしたユーザー ProblemId : 6893 / 自分の提出
問題文最終更新日: 2021-10-23 11:16:13
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 321 (順位表) の他の問題:

Problem Statement

Solve the following problem for each $K=0,1,\ldots,N-1$.

$N$ integers $A_1, A_2, \ldots, A_N$ are written on a blackboard.

You choose exactly $K$ of these integers and rewrite each of them to any integer of your choice between $1$ and $10^6$, inclusive.

You may rewrite an integer to the same integer as the original one.

Find the maximum possible greatest common divisor of the $N$ integers after rewriting.

Original problem: ABC125-C (GCD on Blackboard)

Input

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

  • $2\leq N\leq 2\times 10^5$
  • $1\leq A_i\leq 10^6$
  • All inputs are integers.

Output

Output $N$ lines. On the $i$-th line, output the answer for $K=i-1$.

Sample

Sample 1
Input
3
8 6 12
Output
2
6
12

  • When $K=0$, nothing is rewritten. $\gcd(8,6,12)=2$.
  • When $K=1$, for example, rewriting $8$ to $12$ gives $\gcd(12,6,12)=6$, which is the maximum.
  • When $K=2$, for example, rewriting $8$ to $36$ and $6$ to $24$ gives $\gcd(36,24,12)=12$, which is the maximum.

Sample 2
Input
2
1000000 1000000
Output
1000000
1000000

It is also possible to rewrite an integer to the same integer as the original one.

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