Circle
Circle
https://ac.nowcoder.com/acm/problem/19805
题目
要把 这
个数字首尾连接组成一个环，使得相邻元素互质的对数尽可能多。请输出最大对数。
解题思路
不考虑互质，一共有 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;
}
查看34道真题和解析
投递华为等公司10个岗位 >