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

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$ ($1\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$ ($2\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)。如果有多个解，输出其中任意一个即可。

解题思路

关键观察

1. 约数与因式分解：

   • 我们要找到 (a_i) 的约数。如果我们对 (a_i) 进行因式分解，任何有效的 (d_1) 和 (d_2) 必须满足 (\gcd(d_1 + d_2, a_i) = 1)。
   • 一个简单的观察是，对于每个 (a_i)，如果它有多个不同的质因数，我们可以将这些质因数分成两个非空集合来构造 (d_1) 和 (d_2)。

2. GCD 条件：

   • 最重要的条件是 (\gcd(d_1 + d_2, a_i) = 1)，这意味着 (a_i) 的任何质因数都不应该同时整除 (d_1 + d_2)。

3. 通过筛法高效因式分解：

   • 由于 (a_i) 的最大值可以达到 (10^7)，如果直接对每个 (a_i) 进行因式分解，时间复杂度会非常高。因此，我们可以使用 埃拉托斯特尼筛法 预先计算出每个数的最小质因数（SPF），这使得我们可以在 (O(\log a_i)) 时间内对任意数进行因式分解。

4. 构造 (d_1) 和 (d_2)：

   • 如果 (a_i) 只有一个质因数，那么无法将它拆分成满足条件的两个约数。因此，对于质数的幂次，答案应该是 (-1, -1)。
   • 对于有多个质因数的数，我们可以将质因数分成两个非空集合，计算对应的 (d_1) 和 (d_2)。

算法步骤

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

代码解析

1. Prime 函数：

   • 使用筛法计算每个数的最小质因数，并将所有质数存储在 prime 数组中。

2. 主解法函数 solved：

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

3. 输出结果：

   • 输出两个数组 ans1 和 ans2，分别存储每个数的两个约数。

时间复杂度分析

1. 筛法计算：

   • 筛法的时间复杂度是 (O(A \log \log A))，其中 (A = 10^7)。

2. 因式分解：

   • 对于每个数 (a_i)，使用预计算的最小质因数数组进行因式分解的时间复杂度是 (O(\log a_i))。

3. 总时间复杂度：

   • 总的时间复杂度为 (O(A \log \log A + n \log A))，其中 (A = 10^7) 且 (n \leq 5 \times 10^5)。

结论

该算法通过筛法高效地计算出每个数的最小质因数，然后利用这些质因数进行因式分解，并检查是否能找到满足条件的两个约数。该方法能够高效地处理题目给定的约束。