← 返回题目列表

Codeforces · 1366/D

D. 两个除数

中文机器翻译题面 查看原题

给你 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$。

对于每个 $$$a_i$$$ 找到其两个除数 $$$d_1 > 1$$$ 和 $$$d_2 > 1$$$,使得 $$$\gcd(d_1 + d_2, a_i) = 1$$$ (其中 $$$\gcd(a, b)$$$ 是 $$$a$$$ 的最大公约数, $$$b$$$) 或者说不存在这样的对。

输入

第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 数组 $$$a$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$2 \le a_i \le 10^7$$$) — 数组 $$$a$$$。

输出

要加快输出速度,请打印两行,每行包含 $$$n$$$ 整数。

第一行和第二行中的第 $$$i$$$ 整数应该是相应的除数 $$$d_1 > 1$$$ 和 $$$d_2 > 1$$$,这样 $$$\gcd(d_1 + d_2, a_i) = 1$$$ 或 $$$-1$$$ 和 $$$-1$$$(如果没有这样的对)。如果有多个答案,请打印其中任何一个。

示例

输入 #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

注意

让我们看看 $$$a_7 = 8$$$。它有 $$$3$$$ 除数大于 $$$1$$$:$$$2$$$、$$$4$$$、$$$8$$$。正如您所看到的,任何一对除数的和都可以被 $$$2$$$ 以及 $$$a_7$$$ 整除。

对于 $$$a_{10}=24$$$,还有其他有效的 $$$d_1$$$ 和 $$$d_2$$$ 对,例如 $$$(3, 4)$$$ 或 $$$(8, 3)$$$。您可以打印其中任何一个。