牛客周赛101 D题 题解

原题链接

https://ac.nowcoder.com/acm/contest/113313/D

题目描述

解题思路

很显然无论怎么排列，我们必定有至少一个区间的gcd为1，所以按位或的结果也必定不可能是偶数，所以如果m为偶数则直接无解。
我们可以将二进制位中除了1以外每一个二进制位对应的2的幂作为一个个长度为1的区间，然后把剩下的数拿去单独构造一个区间（gcd必定为1）
注意边界

代码（CPP）

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5 + 10;
const int INF = 0x3fffffff;
const int mod = 1000000007;
bool used[maxn];void solve() {int n, m;cin >> n >> m;if ((m & 1) == 0) {cout << -1 << endl;return;}for (int i = 0; i < 31; i++) {if ((m >> i & 1LL) && (1LL << i) > n) {cout << -1 << endl;return;}}// 先把2的正数幂次选入vector<int> perm;int bits = 0;for (int i = 1; i < 31; i++) {if ((m >> i & 1LL)) {perm.push_back(1 << i);used[1 << i] = true;bits++;}}// 剩余的单独组成一个区间for (int i = 1; i <= n; i++) {if (!used[i]) {perm.push_back(i);}}// 输出排列for (int i = 0; i < perm.size(); i++) {cout << perm[i] << " ";}cout << endl;// 输出区间cout << bits + 1 << endl;for (int i = 1; i <= bits; i++) {cout << i << " " << i << endl;}cout << bits + 1 << " " << n << endl;
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout << fixed;cout.precision(18);solve();return 0;
}