[CF1366D] Two Divisors

Description

有 (n) 个询问，每次给定一个数 (a le 10^7)，求其是否存在两个不为 (1) 的不同因子 (d_1,d_2) 满足 ((d_1+d_2,a)=1)。

Solution

设 (x=p_1^{q_1} p_2^{q_2} ... p_k^{q_k})$，则 (k=1) 时显然无解，考察 (k>1) 时，利用反证法可以证明令 (a=p_1^{q_1}, b=p_2^{q_2} ... p_k^{q_k})，则一定满足 ((a+b,x)=1)。

于是问题转化为寻找一个数的最小质因子。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e7 + 5;
int t, n, minfactor[N];

int main()
{
    for (int i = 1; i < N; i++)
        minfactor[i] = i;
    for (int i = 2; i * i < N; i++)
        if (minfactor[i] == i)
        {
            for (int j = i * i; j < N; j += i)
                if (minfactor[j] == j)
                    minfactor[j] = i;
        }
    ios::sync_with_stdio(false);

    cin >> n;

    vector<int> ans[2];
    while (n--)
    {
        int x;
        cin >> x;
        int t = x;
        while (t % minfactor[x] == 0)
            t /= minfactor[x];
        if (t == 1)
        {
            for (int i = 0; i < 2; i++)
                ans[i].push_back(-1);
        }
        else
        {
            ans[0].push_back(t);
            ans[1].push_back(x / t);
        }
    }

    for (int i = 0; i < 2; i++)
    {
        for (auto x : ans[i])
            cout << x << " ";
        cout << endl;
    }
}