問題一覧 > 通常問題

No.2609 Decreasing GCDs

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 119
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi
1 ProblemId : 6738 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-01-19 15:12:37

問題文

整数 NN が与えられます。NN 個の 11 以上の整数からなる数列 A=(A1,A2,AN)A = \left( A_1 , A_2 , \cdots A_N \right) で以下の 33 つの条件を全て満たすものを 11 つ出力してください。

  • 1iN1 \leq i \leq N を満たす整数 ii に対し、 Ai108A_i \leq 10^8
  • 1iN11 \leq i \leq N-1 を満たす整数 ii に対し、 Ai<Ai+1A_i < A_{i+1}
  • 1iN21 \leq i \leq N-2 を満たす整数 ii に対し、 GCD(Ai,Ai+1)>GCD(Ai+1,Ai+2)\mathrm{GCD} (A_i,A_{i+1}) > \mathrm{GCD} (A_{i+1},A_{i+2}) ( GCD(x,y)\mathrm{GCD} (x,y)xxyy の最大公約数とする)

本問題の制約下で、条件を満たす数列があることは証明できます。

入力

NN

  • 3N253 \leq N \leq 25
  • 入力は全て整数

出力

数列の各要素を以下の形式で空白で区切って一行に出力し、最後に改行してください。
条件を満たす解が複数存在する場合は、どれを出力しても構いません。

A1  A2  ANA_1\ \ A_2\ \ \cdots A_N

サンプル

サンプル1
入力
3
出力
14 21 24

11 つめの条件と 22 つめの条件は明らかに満たされています。
GCD(14,21)=7,GCD(21,24)=3\mathrm{GCD} (14,21) =7,\mathrm{GCD} (21,24) =3 より、 33 つめの条件も満たされていることが分かります。

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