Circle

题目

要把 这 个数字首尾连接组成一个环，使得相邻元素互质的对数尽可能多。请输出最大对数。

解题思路

不考虑互质，一共有 n 对相邻的数。

由更相减损术知，数对 (x-1, x) 的最大公因数与 (1, x-1) 的最大公因数相同，即为 1，互质。
所以，可以将 n 个数字按从小到大的顺序排列并连接，然后将 1 和 n 连接，组成一个环，每对相邻的数都互质。

C++代码

#include<iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    cout << n << endl;
    return 0;
}