当前位置：首页 > article >正文

Two Divisors （ Educational Codeforces Round 89 (Rated for Div. 2) ）

article 2025/2/2 12:13:46

Two Divisors （ Educational Codeforces Round 89 (Rated for Div. 2) ）

You are given $n$ integers $a_1, a_2, \dots, a_n$ .

For each $a_i$ find its two divisors $d_1 > 1$ and $d_2 > 1$ such that $gcd(d_1 + d_2, a_i) = 1$ (where $\gcd(a, b)$ is the greatest common divisor of $a$ and $b$ ) or say that there is no such pair.

Input

The first line contains single integer $n$ ( $\le n \le 5 \cdot 10^5$ ) — the size of the array $a$ .

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $\le a_i \le 10^7$ ) — the array $a$ .

Output

To speed up the output, print two lines with $n$ integers in each line.

The $i$ -th integers in the first and second lines should be corresponding divisors $d_1 > 1$ and $d_2 > 1$ such that $gcd(d_1 + d_2, a_i) = 1$ or $- 1$ and $- 1$ if there is no such pair. If there are multiple answers, print any of them.

Example

Input

10
2 3 4 5 6 7 8 9 10 24

Output

-1 -1 -1 -1 3 -1 -1 -1 2 2 
-1 -1 -1 -1 2 -1 -1 -1 5 3

Note

Let’s look at $a_7 = 8$ . It has $3$ divisors greater than $1$ : $2$ , $4$ , $8$ . As you can see, the sum of any pair of divisors is divisible by $2$ as well as $a_7$ .

There are other valid pairs of $d_1$ and $d_2$ for $a_{10}=24$ , like $(3, 4)$ or $(8, 3)$ . You can print any of them.

问题描述

给定一组整数 (a_1, a_2, \dots, a_n)。对于每个整数 (a_i)，你需要找到两个大于 1 的约数 (d_1) 和 (d_2)，使得：

\gcd(d_1 + d_2, a_i) = 1
$$
如果这样的约数对 (d_1) 和 (d_2) 存在，输出它们。如果不存在，则输出 (-1, -1)。如果有多个解，输出其中任意一个即可。

解题思路

关键观察

约数与因式分解：
- 我们要找到 (a_i) 的约数。如果我们对 (a_i) 进行因式分解，任何有效的 (d_1) 和 (d_2) 必须满足 (\gcd(d_1 + d_2, a_i) = 1)。
- 一个简单的观察是，对于每个 (a_i)，如果它有多个不同的质因数，我们可以将这些质因数分成两个非空集合来构造 (d_1) 和 (d_2)。
GCD 条件：
- 最重要的条件是 (\gcd(d_1 + d_2, a_i) = 1)，这意味着 (a_i) 的任何质因数都不应该同时整除 (d_1 + d_2)。
通过筛法高效因式分解：
- 由于 (a_i) 的最大值可以达到 (10^7)，如果直接对每个 (a_i) 进行因式分解，时间复杂度会非常高。因此，我们可以使用 埃拉托斯特尼筛法 预先计算出每个数的最小质因数（SPF），这使得我们可以在 (O(\log a_i)) 时间内对任意数进行因式分解。
构造 (d_1) 和 (d_2)：
- 如果 (a_i) 只有一个质因数，那么无法将它拆分成满足条件的两个约数。因此，对于质数的幂次，答案应该是 (-1, -1)。
- 对于有多个质因数的数，我们可以将质因数分成两个非空集合，计算对应的 (d_1) 和 (d_2)。

算法步骤

筛法：利用筛法预计算每个数的最小质因数（SPF）。
因式分解：对每个 (a_i) 使用预计算的最小质因数数组来找到它的质因数。
检查有效性：如果 (a_i) 有多个不同的质因数，将它们分成两组，计算 (d_1) 和 (d_2)，并检查 (\gcd(d_1 + d_2, a_i) = 1) 条件。
输出结果：对每个数，输出对应的 (d_1) 和 (d_2) 或者 (-1, -1)。

代码实现

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define int long long
#define Max(a, b) (((a) > (b)) ? (a) : (b))
#define Min(a, b) (((a) < (b)) ? (a) : (b))
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

const int inf = 1e9 + 7;
const int N = 1e7 + 10;

int isPrime[N];
vector<int> prime;

void Prime() {
    for (int i = 2; i < N; ++i) {
        isPrime[i] = 1;
    }
    for (int i = 2; i < N; ++i) {
        if (isPrime[i]) {
            prime.push_back(i);
        }
        for (auto it : prime) {
            if (it * i >= N) {
                break;
            }
            isPrime[it * i] = 0;
            if (i % it == 0) {
                break;
            }
        }
    }
}

void solved() {
    Prime();
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> ans1(n, -1);
    vector<int> ans2(n, -1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    for (int i = 0; i < n; ++i) {
        if (isPrime[a[i]]) {
            continue;
        }
        int x = a[i];
        for (auto it : prime) {
            if (it * it > x) {
                break;
            }
            if (x % it == 0) {
                int y = 1;
                while (x % it == 0) {
                    x /= it;
                    y *= it;
                }
                if (y != a[i] && __gcd(y + x, a[i]) == 1) {
                    ans1[i] = x;
                    ans2[i] = y;
                    break;
                }
                break;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << ans1[i] << ' ';
    }
    cout << endl;
    for (int i = 0; i < n; ++i) {
        cout << ans2[i] << ' ';
    }
}

signed main() {
    BoBoowen;
    int T = 1;
    while (T--) {
        solved();
    }
}

代码解析

Prime 函数：
- 使用筛法计算每个数的最小质因数，并将所有质数存储在 prime 数组中。
主解法函数 solved：
- 首先读取输入数据，然后初始化 ans1 和 ans2 数组来存储每个数的两个约数。
- 对于每个 (a_i)，如果它是质数，则跳过它，因为质数不能拆分成两个约数。
- 对于合成数，通过使用预计算的最小质因数来获取其质因数。如果它有多个不同的质因数，则尝试将质因数分成两组，计算 (d_1) 和 (d_2)，并检查它们的和是否满足 GCD 条件。
输出结果：
- 输出两个数组 ans1 和 ans2，分别存储每个数的两个约数。

时间复杂度分析

筛法计算：
- 筛法的时间复杂度是 (O(A \log \log A))，其中 (A = 10^7)。
因式分解：
- 对于每个数 (a_i)，使用预计算的最小质因数数组进行因式分解的时间复杂度是 (O(\log a_i))。
总时间复杂度：
- 总的时间复杂度为 (O(A \log \log A + n \log A))，其中 (A = 10^7) 且 (n \leq 5 \times 10^5)。