【UR #3】核聚变反应强度 - 题目

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

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

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

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

输入格式

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

第二行 $n$ 个用空格隔开的正整数，第 $i$ 个为 $a_{i}$ 。

输出格式

一行 $n$ 个用空格隔开的整数，第 $i$ 个表示 $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} \leq 10^{9}$
2	$n = 1$ ， $a_{i} \leq 10^{9}$
3	$n \leq 10^{4}$ ， $a_{i} \leq 10^{9}$
4
5
6
7	$n \leq 10^{5}$ ， $a_{i} \leq 10^{12}$
8
9
10

时间限制： $1 s$

空间限制： $256 MB$

下载

样例数据下载

Universal Online Judge

UOJ

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

输入格式

输出格式

样例一

input

output

样例二

input

output

样例三

限制与约定

下载