CF1872C题解

题目大意

给出 $l,r$，构造一组 $a,b$ 使满足以下条件：

• $l \le a+b \le r$
• $\gcd(a,b) \neq 1$

思路

要使 $\gcd(a,b) \neq 1$，也就是 $a$ 与 $b$ 不互质，最简单的就是 $b \mid a$ 或 $a \mid b$。

实现

枚举 $i$ 为 $\gcd(a,b)$ 也就是 $\min(a,b)$，找到一个 $k$ 使 $k \le r$ 且 $i\mid k$，若 $k<l$ 则无解，枚举下一个 $i$。若 $k \ge l$ 则再特判 $\min(i,k-i)$ 是否为 $1$，是则跳过此 $i$，否则输出 $i$ 与 $k-i$。

代码很简单：

#pragma GCC optimize(2,3,"Ofast","inline")
#include<iostream>
using namespace std;
int t,l,r,a,b;
int main(){
	cin>>t;
	while(t--){
		cin>>l>>r;
		for(int i=2;i*i<=r;++i){//这里与判质数同理
			int k=r/i;
			k*=i;
			if(k<l)//a+b是否在l与r之间
				continue;
			if(min(i,k-i)!=1){//再特判
				cout<<i<<' '<<k-i<<endl;
				goto end;//跳出循环
			}
		}
		cout<<"-1\n";
		end:
			continue;
	}
}