Bedan Contest #05 - B - Tổng GCD

View as PDF

Submit solution


Points: 900
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type

Hoán vị của n là các dãy p gồm n phần tử phân biệt từ 1 đến n. Ví dụ [1, 2, 3], [3, 1, 2], [2, 3, 1] là hoán vị của 3, trong khi [1, 2], [3, 4, 2] thì không. Và với mỗi số nguyên dương n, ta sẽ có tất cả n! hoán vị.

Cho số nguyên dương n, hãy tìm hoán vị p của n thỏa mãn:

  • Tồn tại một cặp (i, j) thỏa mãn p_i > p_ji < j.
  • \sum_{i = 1}^n gcd(i, p_{n-i+1}) đạt giá trị nhỏ nhất.

Input and Output

Input
  • Số nguyên dương n (1 \le n \le 10^6).
Output
  • In ra hoán vị p của n bất kỳ thỏa mãn.

Test

Input
4
Output
3 4 1 2
Note
  • Với hoán vị p trên, ta có \sum_{i = 1}^4 gcd(i, p_{n-i+1}) = 4 là nhỏ nhất.
  • Lưu ý rằng không chỉ có hoán vị p trên mới là đáp án đúng.

Comments

There are no comments at the moment.