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;
}