atcoder#AGC022B. [AGC022B] GCD Sequence

    ID: 19374 传统题 2000ms 256MiB 尝试: 2 已通过: 2 难度: 4 上传者: 标签>数学数论最大公约数算法基础构造gcd

[AGC022B] GCD Sequence

Score : 600600 points

Problem Statement

Nagase is a top student in high school. One day, she's analyzing some properties of special sets of positive integers.

She thinks that a set S={a1,a2,...,aN}S = \{a_{1}, a_{2}, ..., a_{N}\} of distinct positive integers is called special if for all 1iN1 \leq i \leq N, the gcd (greatest common divisor) of aia_{i} and the sum of the remaining elements of SS is not 11.

Nagase wants to find a special set of size NN. However, this task is too easy, so she decided to ramp up the difficulty. Nagase challenges you to find a special set of size NN such that the gcd of all elements are 11 and the elements of the set does not exceed 3000030000.

Constraints

  • 3N200003 \leq N \leq 20000

Input

Input is given from Standard Input in the following format:

NN

Output

Output NN space-separated integers, denoting the elements of the set SS. SS must satisfy the following conditions :

  • The elements must be distinct positive integers not exceeding 3000030000.
  • The gcd of all elements of SS is 11, i.e. there does not exist an integer d>1d > 1 that divides all elements of SS.
  • SS is a special set.

If there are multiple solutions, you may output any of them. The elements of SS may be printed in any order. It is guaranteed that at least one solution exist under the given contraints.

3
2 5 63

{2,5,63}\{2, 5, 63\} is special because $gcd(2, 5 + 63) = 2, gcd(5, 2 + 63) = 5, gcd(63, 2 + 5) = 7$. Also, gcd(2,5,63)=1gcd(2, 5, 63) = 1. Thus, this set satisfies all the criteria.

Note that {2,4,6}\{2, 4, 6\} is not a valid solution because gcd(2,4,6)=2>1gcd(2, 4, 6) = 2 > 1.

4
2 5 20 63

{2,5,20,63}\{2, 5, 20, 63\} is special because $gcd(2, 5 + 20 + 63) = 2, gcd(5, 2 + 20 + 63) = 5, gcd(20, 2 + 5 + 63) = 10, gcd(63, 2 + 5 + 20) = 9$. Also, gcd(2,5,20,63)=1gcd(2, 5, 20, 63) = 1. Thus, this set satisfies all the criteria.