题意:现在我们要把1…n这n个数字首尾连接组成一个环,使得相邻元素互质的对数尽可能多。请输出最大对数。
1-n的数字连成一个环,显然如果这些数字从小到大顺次排列,相邻数字之间只差1,则相邻数互质的可能性最大,
又因为1和任何数都互质,所以答案就是直接按顺序排列
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; cout<<n; }
题意:现在我们要把1…n这n个数字首尾连接组成一个环,使得相邻元素互质的对数尽可能多。请输出最大对数。
1-n的数字连成一个环,显然如果这些数字从小到大顺次排列,相邻数字之间只差1,则相邻数互质的可能性最大,
又因为1和任何数都互质,所以答案就是直接按顺序排列
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; cout<<n; }