UOJ Logo Universal Online Judge

UOJ

#48. 【UR #3】核聚变反应强度

统计

著名核物理专家 Picks 提出了核聚变特征值这一重要概念。

核聚变特征值分别为 $x$ 和 $y$ 的两个原子进行核聚变,能产生数值为 $\text{sgcd}(x, y)$ 的核聚变反应强度。

其中, $\text{sgcd}(x, y)$ 表示 $x$ 和 $y$ 的次大公约数,即能同时整除 $x, y$ 的正整数中第二大的数。如果次大公约数不存在则说明无法核聚变, 此时 $\text{sgcd}(x, y) = -1$。

现在有 $n$ 个原子,核聚变特征值分别为 $a_1, a_2, \dots, a_n$。然后 Picks 又从兜里掏出一个核聚变特征值为 $a_1$ 的原子,你需要计算出这个原子与其它 $n$ 个原子分别进行核聚变反应时的核聚变反应强度,即 $\text{sgcd}(a_1, a_1), \text{sgcd}(a_1, a_2), \dots, \text{sgcd}(a_1, a_n)$。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个用空格隔开的正整数,第 $i$ 个为 $a_i$。

输出格式

一行 $n$ 个用空格隔开的整数,第 $i$ 个表示 $\text{sgcd}(a_1, a_i)$。

C/C++ 输入输出 long long 时请用 %lld由于本题数据量较大,建议不要使用 cin/cout 进行输入输出。

样例一

input

4
12450 1 2 450

output

6225 -1 1 75

样例二

input

8
30030 6 10 12 55 36 450 666

output

15015 3 5 3 11 3 15 3

样例三

见样例数据下载。

限制与约定

测试点编号 $n$、$a_i$的规模
1$n = 1$,$a_i \le 10^9$
2
3$n \le 10^4$,$a_i \le 10^9$
4
5
6
7$n \le 10^5$,$a_i \le 10^{12}$
8
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载