Problem - C - Codeforces

题目大意:给出t个区间l,r,要求在每个区间内找到两个数a,b满足l<=a+b<=r,且gcd(a,b)!=1

1<=t<=500;1<=l<=r<=1e7

思路:记个结论:gcd(a,b-a)=gcd(a,b)

然后如果区间内有偶数就将其平分,如果只有奇数,就取一个非1的因数即可满足条件,因数和他倍数的gcd就是那个因数

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
const int N = 500 + 5;
typedef long long ll;
pair<int, int>a[105];
int n;
void init()
{

}
void solve()
{
	int l, r;
	cin >> l >> r;
	if (l!=r||(l==r&&r%2==0))
	{
		if (r <4)
		{//偶数不能是2,因为不能拆出1
			cout << -1 << endl;
			return;
		}
		if (r & 1)
		{
			cout << (r - 1) / 2 << " " << (r - 1) / 2 << endl;
		}
		else
		{
			cout << r / 2 << " " << r / 2 << endl;
		}
		return;
	}
	else
	{
		for (int i = 3; i * i <= l; i++)
		{
			if (l % i == 0)
			{
				cout << i << " " << l - i << endl;
				return;
			}
		}
		cout << -1 << endl;
	}
	init();
	
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
}
09-14 11:53