Educational Codeforces Round 89 (Rated for Div. 2) D. Two Divisors（数论、gcd）

题面：

题意：
给定一个长度为n的数组a。
对于数组a中每一个数 ai，找到ai 两个大于1的因子x，y，使得gcd(x+y,a)=0。

题解：

记录每个数的最小质因子，然后分解，时间复杂度好像是 $O (l o g n)$ 的。

（1）如果 $a_{i}$ 本质不同的质因子只有一个，那么找不到 $d_{1}, d_{2}$
（2）否则我们设 $a = p_{1}^{s_{1}} p_{2}^{s_{2}} . . . p_{k}^{s_{k}}, d_{1} = p_{1} * p_{2} . . . p_{x}, d_{2} = p_{x + 1} . . . p_{k}$

证明：对于任意一个 $p_{i} ， a <mtext> </mtext> m o d <mtext> </mtext> p_{i} = 0, (d_{1} + d_{2}) <mtext> </mtext> m o d <mtext> </mtext> p_{i} \neq 0$ ，因为要么 $d_{1} <mtext> </mtext> m o d <mtext> </mtext> p_{i} = 0, d_{2} <mtext> </mtext> m o d <mtext> </mtext> p_{i} \neq 0$ 要么 $d_{1} <mtext> </mtext> m o d <mtext> </mtext> p_{i} \neq 0, d_{2} <mtext> </mtext> m o d <mtext> </mtext> p_{i} = 0$

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=10000100;
const int maxp=1100;
const int maxm=500100;
const int up=100000;

int prime[maxn],cnt=0;
int ha[maxn],d1[maxm],d2[maxm];

void Prime(void)
{
    ha[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!ha[i])
        {
            ha[i]=i;
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt&&prime[j]*i<maxn;j++)
        {
            ha[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        }
    }
}

int main(void)
{
    Prime();
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        d1[i]=1,d2[i]=1;
        while(x>1)
        {
            while(ha[x/ha[x]]==ha[x]) x/=ha[x];
            if(d1[i]==1) d1[i]*=ha[x];
            else d2[i]*=ha[x];
            x/=ha[x];
        }
        if(d2[i]==1)
            d1[i]=-1,d2[i]=-1;
    }
    for(int i=1;i<=n;i++)
        printf("%d ",d1[i]);
    putchar('\n');
    for(int i=1;i<=n;i++)
        printf("%d ",d2[i]);
    putchar('\n');
    return 0;
}