Two Divisors

发表于 更新于 分类于 ，

    给出n个数，求每个数x能否找到两个都大于1的因子d1和d2，使得gcd(d1+d2, x) = 1

    如果不能则输出-1,-1.

Two Divisors

Created by LXC on Thu May 11 10:54:58 2023

https://codeforces.com/problemset/problem/1366/D

ranting: 2000

tag: constructive algorithms, math, number theory

题意

给出n个数，求每个数x能否找到两个都大于1的因子d1和d2，使得gcd(d1+d2, x) = 1
如果不能则输出-1,-1.

题解

如果x的质因子分解后不同质因子的个数只有1个。
那么没有答案

否则设不同质因子分别为$p_1, p_2, \cdots, p_k$，我们将其分为两个集合$p_1,p_2,\cdots, p_i$和$p_{i+1}, p_{i+2}, \cdots, p_k$。

我们发现$x$中的每个因子$p_i$只能整除$\prod \limits_{j=1}^{i} p_j $和$ \prod \limits_{j=i+1}^{k} p_j$其中一个，所以$\prod \limits_{j=1}^{i} p_j + \prod \limits_{j=i+1}^{k} p_j$和$x$的最大公因数为1.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 10000005
// #define N 105
#define MOD 998244353
using namespace std;

vector<int> p;
int lpf[N];

void sieve() {
    lpf[1] = 1;
    for (int i = 2; i < N; i++) {
        if (lpf[i] == 0) {
            lpf[i] = i;
            p.push_back(i);
        }
        for (int j = 0; p[j] * i < N; j++) {
            lpf[p[j] * i] = p[j];
            if (i % p[j] == 0) {
                break;
            }
        }
    }
    // for (int i : p) {
    //     cout << i << "\n";
    // }
    // for (int i = 1; i < N; i++) {
    //     cout << i << " " << lpf[i] << "\n";
    // }
}

void sol() {
    int n;
    cin >> n;
    vector<int> a(n, -1), b(n, -1);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        vector<int> fac;
        while (lpf[x] != 1) {
            if (fac.empty() || fac.back() != lpf[x])
                fac.push_back(lpf[x]);
            x /= lpf[x];
        }
        int mult = 1;
        for (int j : fac) {
            // cout << j << " ";
            mult *= j;
        }
        // cout << "\n";
        if (fac.size() > 1) {
            a[i] = fac[0];
            b[i] = mult / fac[0];
        }
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << "\n";
    for (int i = 0; i < n; i++) {
        cout << b[i] << " ";
    }
    cout << "\n";
}

/*
TLE O(n sqrt(n))
void sol() {
    int n;
    cin >> n;
    vector<int> a(n, -1), b(n, -1);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        vector<int> fac;
        for (int j = 2; j * j <= x; j++) {
            if (x % j)
                continue;
            fac.push_back(j);
            while (x % j == 0)
                x /= j;
        }
        if (x != 1) {
            fac.push_back(x);
        }
        int mult = 1;
        for (int j : fac) {
            // cout << j << " ";
            mult *= j;
        }
        // cout << "\n";
        if (fac.size() > 1) {
            a[i] = fac[0];
            b[i] = mult / fac[0];
        }
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << "\n";
    for (int i = 0; i < n; i++) {
        cout << b[i] << " ";
    }
    cout << "\n";
}
*/
int main() {
    sieve();
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}