Codeforces Round 895 (Div. 3) C题QAQ原理秒杀

Problem - C - Codeforces

这是个有关公约数的题

题目大意：给你，现在你需要找到，满足一下要求：

1、l ≤ a+b ≤ r

2、gcd(a,b) ≠ 1

若a,b有多组答案，你可以输出其中任意一种，若不存在解输出-1。

输入描述：第一行输入和，含义如上文。，最多500组测试样例

输出描述：请输出一组和作为答案。

(作者：冬权九暮 https://www.bilibili.com/read/cv26418408/?spm_id_from=333.999.0.0 出处：bilibili)

解法：

这道题直接分两种情况

1.l == r

l既然等于r，那么我们要找的数（假设a和b）的和就为l，即a + b = l；我们遍历一遍就可以知道有没有  （两个数是确定的）

2.l != r

l不等于r，那么范围最小的情况就是l + 1 = r，l 和 r中肯定有一个偶数！

那么这个偶数 - 2和2即为答案

（当然，当l  = 2，r = 3这种情况就没有，所以r至少为4）

参考代码

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <math.h> 
 
int main()
{
    int t;
    cin >> t;
    int l, r;
    for (int k = 0; k < t; k++)
    {
        cin >> l >> r;
        //2 2
        bool tmp = true;
        int a, b;
        if (r < 4)tmp = false;
        else if (r == l)
        {
            b = 0;
            for (a = 2; a <= sqrt(l); a++)
            {
                if ((l - a) % a == 0)
                {
                    b = l - a;
                    break;
                }
            }
            if(b == 0)tmp = false;
        }
        else if (r >= 4)
        {
            if (r % 2 == 0)
            {
                a = 2;
                b = r - 2;
            }
            else
            {
                a = 2;
                b = r - 3;
            }
        }
        //else if(l>=4)
        if (!tmp)cout << "-1" << endl;
        else
        {
            cout << a << " " << b << endl;
        }
    }
    return 0;
}