CF1629B GCD Arrays

题目简述

题目传送门

给你一个长度为 $N$ 的 $a$ 数组（$a$ 数组的元素是 $l$ 到 $r$ 区间中的整数），你可以进行 $k$ 此操作，每次操作可以选择两个数，将他们的乘积加入 $a$ 数组并且删除这两个数，问 $k$ 此操作后能否使 $\gcd(a)$ 大于 $1$

思路

很容易想到要让每个奇数与偶数相乘，很容易算出数组中的奇数个数（即最小操作次数），并且对 $L = R$ 特判即可

代码

#include <bits/stdc++.h>
using namespace std;
 
template<class T>
inline char read(T &ret) {
	ret = 0;
	char c = getchar();
	short f = 1;
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c <= '9' && c >= '0') {
		ret = (ret << 3) + (ret << 1) + c - 48;
		c = getchar();
	}
	ret *= f;
	return c;
}
 
int T;
int L , R , K;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	while(T--) {
		cin >> L >> R >> K;
		int Count = 0;
		if(L % 2 == 0 && R % 2 == 1) {
			Count = (R - L + 1) / 2;
		}
		else if(L % 2 == 0 && R % 2 == 0) {
			Count = (R - L + 1) / 2 + 1;
		}
		else if(L % 2 == 1 && R % 2 == 0) {
			Count = (R - L + 1) / 2;
		}
		else if(L % 2 == 1 && R % 2 == 1) {
			Count = (R - L + 1) / 2;
		}
		if(L == R) {
			if(L == 1) cout << "NO" << endl;
			else if(L != 1) cout << "YES" << endl;
		}
		else if(R - L + 1 - Count > K) cout << "NO" << endl; 
		else cout << "YES" << endl;
	}
	return 0;
}