CF1872C-Non-coprime-Split-题解

title: CF1872C Non-coprime Split 题解
date: 2023-09-18 21:09:14
categories: 
 - 题解

一个很怪的分讨想法。

当 \(l \neq r\) 时，区间内一定有一个偶数。设最大的偶数为 \(x\) ，那么当 \(x > 2\) 时，可以得到一组解 \((2,x-2)\)，此时 \(\gcd(2,x-2) = 2\)。

当 \(l = r\) 时，问题转化为找 \(a+b=l\) 且 \(\gcd(a,b) \neq 1\) 的一组解。当 \(l\) 不为质数时，设有 \(l\) 的因数 \(x\)，那么 \((x,l-x)\) 是一组解，此时 \(\gcd(x,l-x)\) 一定不为 1。

剩余情况无解，时间复杂度 \(O(t\sqrt l)\)。

code：

#include<iostream>
#include<cstdio>
using namespace std;
int t,l,r;
signed main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&l,&r);
		if(l!=r)
		{
			int cnt=r-r%2;
			if(cnt==2)puts("-1");
			else printf("%d %d\n",2,cnt-2);
		}
		else
		{
			bool f=0;
			for(int i=2;i*i<=l;i++)
			{
				if(l%i)continue;
				f=1;
				printf("%d %d\n",i,l-i);
				break;
			}
			if(!f)puts("-1");
		}
	}
}