CF 1872 C

C. Non-coprime Split

这道题可以先进行分类讨论。

• 当\(r<=3\)时皆无解，先排除。
• 当\(l≤x≤r\)中存在\(x\)为偶数时，就能直接找到答案\(a=b=x/2\)
• 当\(l=r\)且\(l\)为奇数时，可以使用朴素求因数的方法判断是否存在\(j\)（\(2≤j≤\sqrt[2]{l}\)）使\((a-j)\mod j=0\)，若存在，则找到答案\(a=j,b=a-j\)。

※不要先用筛子筛出所有质数再进行判断，会超时！！！

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;

const ll N = 1e7 + 10;
ll a, b, t;

signed main()
{
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> a >> b;
        if(b < 4)
        {
            cout << -1 << endl;
            continue;
        }
        if(b - a || b & 1 == 0 || a & 1 == 0)
        {
            cout << ((b - (b & 1)) >> 1) << " " << ((b - (b & 1)) >> 1) << endl;
        }
        else
        {
            bool judge = 0;
            int si = sqrt(a);
            for(int j = 2;j <= si;j++)
            {
                if((a - j) % j == 0)
                {
                    judge = 1;
                    cout << j << " " << a - j << endl;
                    break;
                }
            }
            if(!judge)
            {
                cout << "-1" << endl;
            }
        }
    }
    return 0;
}