AC题解

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        long long l, r, k;
        cin >> l >> r >> k;
        long long m = r - l + 1;
        if (l == r) {
            if (l > 1) {
                cout << "YES\n";
            }else{
                cout << "NO\n";
            }
            continue;
        }
        if (l == 1) {
            long long e = (r - 2) / 2 + 1; 
            long long o = m - e; 
            if (k >= o) {
                cout << "YES\n";
            }else{
                cout << "NO\n";
            }
            continue;
        }
        long long e, o;
        if (r % 2 == 0) {
            e = (r - l) / 2 + 1;
        }else{
            e = (r - 1 - l) / 2 + 1;
        }
        o = m - e;
        if (k >= o) {
            cout << "YES\n";
        }else{
            cout << "NO\n";
        }
    }
    return 0;
}

这段代码的核心功能是：判断在区间 [l, r] 组成的序列中，经过 k 次指定操作后，剩余数字的公因数能否大于 1，最终输出 YES 或 NO（多组测试用例）。

核心逻辑

要让剩余数字的公因数 > 1，最容易实现的方式是让所有剩余数字都包含同一个质因数（优先选 2，因为偶数天然含质因数 2，无需额外找其他质因数）。所以代码的核心是：判断能否通过 k 次操作，消去区间内所有奇数（留下的全是偶数，公因数至少为 2）。

代码逐段解释

1. 输入处理与初始化

int t;
cin >> t;
while (t--) {
    long long l, r, k;
    cin >> l >> r >> k;
    long long m = r - l + 1;

• t：测试用例的组数。
• l, r：序列的区间边界，k：允许的操作次数。
• m：序列的总元素个数（区间内整数的数量）。

2. 特殊情况 1：区间只有一个元素（l == r）

if (l == r) {
    if (l > 1) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
    continue;
}

• 若单个元素 > 1（如 3），它的公因数就是自己，天然 > 1 → 输出 YES。
• 若单个元素是 1，公因数是 1 → 输出 NO。
• continue：跳过后续逻辑，直接处理下一组测试用例。

3. 特殊情况 2：区间包含 1（l == 1）

if (l == 1) {
    long long e = (r - 2) / 2 + 1; 
    long long o = m - e; 
    if (k >= o) {
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
    continue;
}

• 1 是特殊值：它没有质因数 > 1，且与任何数相乘仍为原数，会破坏 “公因数> 1” 的条件，必须通过操作消去。
• e：计算 2 到 r 之间的偶数个数（因为 1 是奇数，单独统计）。
• o：区间内的奇数总数（含 1）= 总元素数 m- 偶数个数 e。
• 消去所有奇数需要 o 次操作（每个奇数需与一个数相乘，消去 1 个奇数）：
  • 若 k ≥ o → 能消去所有奇数，剩余全是偶数 → 输出 YES。
  • 否则 → 输出 NO。

4. 通用情况：区间不含 1（l ≥ 2）

long long e, o;
if (r % 2 == 0) {
    e = (r - l) / 2 + 1;
} else {
    e = (r - 1 - l) / 2 + 1;
}
o = m - e;
if (k >= o) {
    cout << "YES\n";
}else{
    cout << "NO\n";
}

• 第一步：计算区间内的偶数个数 e：
  • 若 r 是偶数（如 l=4, r=8）：偶数个数 = (8-4)/2 + 1 = 3（4、6、8）。
  • 若 r 是奇数（如 l=2, r=7）：先算到 r-1（6），偶数个数 = (6-2)/2 + 1 = 3（2、4、6）。
• 第二步：计算奇数个数 o = 总元素数 m - 偶数个数 e。
• 第三步：判断操作次数是否足够消去所有奇数：
  • 若 k ≥ o → 能消去所有奇数，剩余全是偶数（公因数 ≥2）→ 输出 YES。
  • 否则 → 输出 NO。

关键总结

代码通过 “优先让剩余数字全为偶数” 的思路，简化了 “公因数 >1” 的判断（无需考虑其他质因数），同时处理了 “单个元素”“包含 1” 等特殊场景，逻辑高效且覆盖所有测试情况。