Educational Codeforces Round 89 (Rated for Div. 2) D. Two Divisors

题意：

每一组给出一个数 (m~(2 leq m leq 10^7)) ，找到数 (m) 的两个大于 (1) 的因数 (d_1) 和 (d_2) ，使得 (gcd(d_1+d_2,m)=1)，存在则输出任意一组，否则答案为 (-1) ;
一共有 (n~(1 leq n leq 5 cdot 10^5)) 组测试数据，时限 (2s) ;

分析：

首先最大公约数有两个基本性质

1. (gcd(a,b)=gcd(a pm b,b)=gcd(a,b pm a);)
2. (if(gcd(a,b)==1)~gcd(a,bc)=gcd(a,c);)

我们考虑把数分解质因数，则 (m=p_1^{k_1} cdot p_2^{k_2} cdots p_g^{k_g})，考虑 (d_1=p_1^{k_1}~,~d_2=p_2^{k_2} cdots p_g^{k_g})，那么首先可以确定

1. (gcd(d_1,d_2)=1;)
2. (m=d_1 cdot d_2;)

因为 (gcd(d_1+d_2,d_1)=gcd(d_1+d_2,d_2)=1)，
则 (gcd(d_1+d_2,m)=gcd(d_1+d_2,d_1 cdot d_2)=gcd(d_1+d_2,d_1)=1;)

那么只要 (m) 至少有两个不同的素因数就一定有解，介于题目的规模，所以得先用欧拉筛 求出每个数的最小素数；

代码：

#include<bits/stdc++.h>
using namespace std;
#define li long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define frep(i,a,b) for(int i=a;i>=b;i--)
const int N = 5E5+10;
const int M = 1E7+10;

int pr[M],minpr[M],cnt;
int ANS[N][2]; 

void eular(int n)
{
	rep(i,2,n){
		if(!minpr[i]) pr[++cnt]=i,minpr[i]=i;
		for(int j=1;j<=cnt&&i*pr[j]<=n;j++){
			minpr[i*pr[j]]=pr[j];
			if(i%pr[j]==0)break;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	eular(1e7);
	int n,x,a;
	cin>>n;
	rep(i,1,n){
		cin>>a; x=a;
		int now=1;
		while(x%minpr[a]==0) now*=minpr[a],x/=minpr[a];
		if(now!=1&&x!=1) ANS[i][0]=now,ANS[i][1]=x;  
		else ANS[i][0]=ANS[i][1]=-1;	
	}
	rep(i,1,n)cout<<ANS[i][0]<<" ";
	cout<<endl;
	rep(i,1,n)cout<<ANS[i][1]<<" ";
}