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