307507: CF1366D. Two Divisors
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Two Divisors
题意翻译
给定 $n$ 个数 $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$。 $n\leq 5\times 10^5 , 2\le a_i\le 10^7$题目描述
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.输入输出格式
输入格式
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 $ .
输出格式
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.
输入输出样例
输入样例 #1
10
2 3 4 5 6 7 8 9 10 24
输出样例 #1
-1 -1 -1 -1 3 -1 -1 -1 2 2
-1 -1 -1 -1 2 -1 -1 -1 5 3