[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;
    }
}

[CF1366D] Two Divisors - 数论

原文：https://www.cnblogs.com/mollnn/p/14082370.html