You are given 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛.

For each 𝑎𝑖 find its two divisors 𝑑1>1 and 𝑑2>1 such that gcd(𝑑1+𝑑2,𝑎𝑖)=1 (where gcd(𝑎,𝑏) is the greatest common divisor of 𝑎 and 𝑏) or say that there is no such pair.

链接 🔗

「CodeForces 1198C」 Matching vs Independent Set

题解 ❓

如果 gcd(p,q)==1gcd(p,q) == 1
那么 gcd(p+q,q)==1gcd(p+q,q)==1gcd(p+q,p)==1gcd(p+q,p)==1

如果 gcd(p+q,p)==1gcd(p+q,p) == 1
那么 gcd(p+q,pq)==1gcd(p+q,p*q)==1

因此有 gcd(p+q,qpk)==1gcd(p+q,q*p^k) == 1
因此找到两个因数,使得 a[i]=qpka[i] = q*p^k 即可

代码

const int N = 1e7+10;
const int NN = 5e5+10;
ll vis[N],a[NN],b[NN],c[NN];
int main()
{
//    __IN;__OUT;
    FOR(i,2,N)
        if(!vis[i])
            for(ll j = i;j<=N;j+=i)
                if(!vis[j]) vis[j] = i;
    ll n;RLL(n);
    FOR(i,1,n)
    {
        RLL(a[i]);
        ll y = a[i],x = vis[a[i]];
        while(y%x == 0) y/=x;
        b[i] = c[i] = -1;
        if(y!= 1 && gcd(y,x) == 1) b[i] = vis[a[i]],c[i] = y;
    }
    FOR(i,1,n) PLP(b[i]); PN();
    FOR(i,1,n) PLP(c[i]);
    return 0;
}