牛客寒假算法基础集训营1I-限制不互素对的排列 题解

题目大意

输入一个数n，请构造一个长度为n的排列，使得其中正好有k对相邻的数gcd大于1。

解题思路

题目难度面向小白，就邪门，我应该还没到小白的水平。

刚开始根本没想到可以用2的倍数来构造。

主要是没想到怎么构造相邻的gcd大于1的数，很明显，2的倍数是最优解。

那么就可以分为两种情况。

一个长度为n的排列中，最多有$\frac{n}{2}$个偶数，即最多有$\frac{n}{2}-1$对。

如果$k\leq \frac{n}{2}-1 $，只需要输出前$k+1$个偶数，然后后面跟着全部输出，最后输出之前漏掉的奇数。

如果$k=\frac{n}{2}$，就需要多出一个对，显然3和6是最优解，所以只需要输出全部的偶数，并且把6放到最后来输出，然后输出3，最后输出之前的奇数。

所以如果当$k=\frac{n}{2}$时，需要满足$n\ge6$。

在上面的构造中用到了两个定理，一个是相邻两个数gcd一定为1，一个是相邻奇数gcd一定为1。

简单的证明一下。

假设相邻奇数gcd不为1。

假设小的那个奇数为a，大的为a+2。

a可以表示为$p_1\times p_2\times \cdots p_n$，其中p为奇数。

a+2可以表示为$p’_1 \times p’_2 \times \cdots p’_n$，其中p‘为奇数。

设gcd为$p_1$。

那么$(a+2)-a=p_1\times(p_2\times \cdots p_n-p’_2 \times \cdots p’_n)=2$。

显然不成立。

得证。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define endl '\n'
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b, ll mod) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans = (ans * a) % mod;
		a = (a * a) % mod, b >>= 1;
	}
	return ans % mod;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int n, k; cin >> n >> k;
	if (k == n / 2) {
		if (n < 6) {
			cout << -1 << endl;
			return 0;
		}
		for (int i = 2; i <= n; i += 2) {
			if (i == 6) continue;
			cout << i << ' ';
		}
		cout << 6 << ' ' << 3;
		for (int i = 1; i <= n; i += 2) {
			if (i == 3)  continue;
			cout << ' ' << i;
		}
		cout << endl;
	}
	else {
		for (int i = 2; i <= 2 * (k + 1); i += 2) {
			cout << i << ' ';
		}
		rep(i, 2 * (k + 1) + 1, n)	cout << i << ' ';
		for (int i = 1; i <= 2 * (k + 1); i += 2) {
			cout << i;
			if (i + 2 >= 2 * (k + 1))	cout << endl;
			else cout << ' ';
		}
	}
	return 0;
}