B. GCD Arrays
题源：https://codeforces.com/contest/1629/problem/B
题目大意
给出一段区间[l, r]，可以进行操作（把任意两个数拿出来，把他俩乘积放回去），如果经过 k 次该操作后，能找到两个数a, b, 使得 gcd(a, b) > 1，就输出"YES",否则输出"NO"
思路
- 如果要使得整个数组的GCD大于 1，每个元素都必须具有一个共同的质因数，因而很容易得出 2 是最常见的质因数。
又因为偶数一定有 2 这个因子，因此我们只需要对奇数进行操作即可
所以要做的就是统计出[l, r]内有多少个奇数，而这有个公式（是我没学过的）要记下来
统计一段区间内的奇数个数: \((r−l+1)−(r/2−(l−1)/2)\)
4.奇数的个数cnt大于 k 的话就没法实现啦
我滴代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int t;
int main (){
cin >> t;
while (t --){
int l, r, k;
cin >> l >> r >> k;
if (l == r){
if (l == 1)
cout << "NO" << endl;
else
cout << "YES" << endl;
continue;
}
int cnt = (r - l + 1) - (r / 2 - (l - 1) / 2);//长知识
if (cnt <= k)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
博客园的第一篇博客(●'◡'●)
