← 返回题目列表

AtCoder · agc022_b

B. GCD 序列

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

长濑是高中的尖子生。有一天,她正在分析特殊正整数集的一些属性。

她认为一套 S = \{a_{1}, a_{2}, ..., a_{N}\} of 不同 正整数称为 特别 如果对于所有 1 \leq i \leq N,gcd(最大公约数) a_{i} 以及剩余元素的总和 S is 不 1.

长濑想要找到一个 特别 套尺寸 N。不过,这个任务太简单了,所以她决定加大难度。长濑挑战你找到一个 特别 套尺寸 N 使得所有元素的 gcd 为 1 并且集合的元素不超过 30000.

约束

  • 3 \leq N \leq 20000

输入

输入由标准输入按以下格式给出:

N

输出

输出 N 以空格分隔的整数,表示集合的元素 S. S 必须满足以下条件:

  • 元素必须是 不同 不超过的正整数 30000.
  • 所有元素的 gcd S is 1,即不存在整数 d > 1 划分所有元素 S.
  • S 是 特别 设置。

如果有多个解决方案,您可以输出其中任何一个。的要素 S 可以按任何顺序打印。保证在给定的约束下至少存在一种解。


示例输入 1

3

示例输出 1

2 5 63

\{2, 5, 63\} 很特别,因为 gcd(2, 5 + 63) = 2, gcd(5, 2 + 63) = 5, gcd(63, 2 + 5) = 7。另外, gcd(2, 5, 63) = 1。因此,该集合满足所有标准。

请注意 \{2, 4, 6\} 不是有效的解决方案,因为 gcd(2, 4, 6) = 2 > 1.


示例输入 2

4

示例输出 2

2 5 20 63

\{2, 5, 20, 63\} 很特别,因为 gcd(2, 5 + 20 + 63) = 2, gcd(5, 2 + 20 + 63) = 5, gcd(20, 2 + 5 + 63) = 10, gcd(63, 2 + 5 + 20) = 9。另外, gcd(2, 5, 20, 63) = 1。因此,该集合满足所有标准。