atcoder#AGC022B. [AGC022B] GCD Sequence
[AGC022B] GCD Sequence
Score : 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 of distinct positive integers is called special if for all , the gcd (greatest common divisor) of and the sum of the remaining elements of is not .
Nagase wants to find a special set of size . However, this task is too easy, so she decided to ramp up the difficulty. Nagase challenges you to find a special set of size such that the gcd of all elements are and the elements of the set does not exceed .
Constraints
Input
Input is given from Standard Input in the following format:
Output
Output space-separated integers, denoting the elements of the set . must satisfy the following conditions :
- The elements must be distinct positive integers not exceeding .
- The gcd of all elements of is , i.e. there does not exist an integer that divides all elements of .
- is a special set.
If there are multiple solutions, you may output any of them. The elements of may be printed in any order. It is guaranteed that at least one solution exist under the given contraints.
3
2 5 63
is special because $gcd(2, 5 + 63) = 2, gcd(5, 2 + 63) = 5, gcd(63, 2 + 5) = 7$. Also, . Thus, this set satisfies all the criteria.
Note that is not a valid solution because .
4
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, . Thus, this set satisfies all the criteria.