1.题目链接。是一个构造的题目，其实题目中已经有了一定的提示：2*k<=n.首先我们知道对于自然数1234...n这个排列一定是权值最小的，因为他们两两互质，gcd(ai,ai+1)=1.不可能比他更小,它的权值和是n-1。那么第二小是多少？第二小最少是n。那么有没有可能是n？？其实很简单，我们知道gcd的几个性质:gcd(k,2*k)=k,所以我们每次只需要调换这个k的位置，就会让这个序列的权值增加k。考虑这样一种序列：2 3 4 5..k-1 k 2*k 1 k+1 .... 2k-1 2k+1 ....n.这个序列其实就是我们需要的。因为gcd(2k+1,2k-1)=1
gcd(k,2*k)=k,其他位置都是1，所以整个序列的权值增加k。具有比较高的技巧性。
#include<bits/stdc++.h> using namespace std; #pragma warning(disable:4996) int main() { int T; scanf("%d", &T); for (int cas = 1; cas <= T; cas++) { int n, k; cin >> n >> k; cout << "Case #" << cas << ": "; if (k == 1) { cout << 1; for (int i = 2; i <= n; i++) cout << " " << i; cout << endl; continue; } for (int i = 2; i <= k - 1; i++) cout << i << " "; cout << k << " " << 2 * k << " " << 1; for (int i = k + 1; i <= 2 * k - 1; i++) cout << " " << i; for (int i = 2 * k + 1; i <= n; i++) cout << " " << i; cout << endl; } return 0; }
