CF1872C Non-coprime Split

One_JuRuo · 2023-09-08 07:49:33 · 题解

思路

CF 典型的诈骗题。

假设分出来的 a 和 b 都有因子 k，那么 a+b 也一定有因子 k，并且至少还存在另一个最小为 2 的因子，才能分出 a 和 b。

所以可以发现，质数是不满足要求的，考虑一个合数，一定可以拆成 k\times a 的形式，那么就直接构造成 k 和 k\times (a-1) 就满足条件了。

所以我们可以提前线性筛预处理出每个数的最小质因子，然后遍历 n 到 m，找到第一个合数，然后直接拆开就好了。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,m,su[10000005],pri[10000005],cnt,minp[10000005],flag;
inline void init()
{
    for(int i=2;i<=10000000;++i)
    {
        if(!su[i]) pri[++cnt]=i,minp[i]=i;
        for(int j=1;j<=cnt&&i*pri[j]<=10000000;++j)
        {
            su[i*pri[j]]=1,minp[i*pri[j]]=pri[j];
            if(i%pri[j]==0) break;
        }
    }
}
int main()
{
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m),flag=0;
        for(int i=max(2,n);i<=m;++i) if(i/minp[i]>1){flag=1,printf("%d %d\n",minp[i],i-minp[i]);break;}
        if(!flag) printf("-1\n");//记得判无解
    }
}