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)。