Circle
Circle
https://ac.nowcoder.com/acm/contest/6226/B
题目描述 :
现在我们要把1到这n个数字首尾连接组成一个环，使得相邻元素互质的对数尽可能多。请输出最大对数。
输入描述:
一行一个整数n(1≤ n≤ 1000)。
输出描述:
一行一个整数表示答案。
思路：
两个数字A,B互质等价于A，B的最大公约数为1。根据我们的数学知识可以知道：
1，任意相邻两数的最大公约数为1；
2，1与任何大于0的数字的最大公约数都是1本身。
综上可知，将这n个数字按照大小顺序首尾顺序排列即可使得相邻元素互质的对数尽可能多。
参考代码如下：
#include<iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
cout << n << endl;
return 0;
}
查看18道真题和解析