题目描述

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

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

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

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

输入格式

第一行包含一个正整数 $n$ ($n \leq 10^5$)。

第二行包含 $n$ 个用空格隔开的正整数，第 $i$ 个为 $a_i$ ($a_i \leq 10^{12}$)。

输出格式

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

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

题解

由数论性质，$a, b$ 的公约数一定是 $\gcd(a, b)$ 的因数，因此我们所要求的 $\mathrm{sgcd}(a, b)$ 就等于 $d = \gcd(a, b)$ 的次大因数，即 $d$ 除以 $d$ 的最小素因子。

因此有一个暴力算法，筛出 $10^6$ 以内的素数后，每次令 $d_i = \gcd(a_1, a_i)$ 后，暴力寻找 $d_i$ 的最小素因子。

但是它的时间复杂度为 $O \left( n \dfrac {\sqrt {a_i}} {\log a_i} \right)$ 的，超出了限制 (然而能水过 90 分？)，我们需要优化它 (当然你用 Pollard-Rho 我无话可说)。

其实我们并不需要枚举 $10^6$ 以内的每个素数，因为由于 $d_i \mid a_1$，因此 $d_i$ 的素因子一定是 $a_1$ 的素因子。因此我们只需把 $a_1$ 分解质因数，然后取它的所有不同素因子，让这些素因子去试除 $d_i$。

由于一个数 $n$ 的素因子的个数是 $O(\log n)$ 的，故总时间复杂度为 $O \left( \sqrt {a_1} + n \log a_1 \right)$。

代码

#include <bits/stdc++.h>
#define N 100034
#define M 1024404
using namespace std;

typedef long long ll;

int n, cnt = 0;
ll A, B, i, p[30];

int main(){
	scanf("%d%lld", &n, &A);
	for(B = A, i = 2; i * i <= B; ++i)
		if(!(B % i)) for(p[++cnt] = i; !(B % i); B /= i);
	if(B > 1) p[++cnt] = B; p[++cnt] = -1;
	printf("%lld\n", A / p[1]);
	for(; --n; ){
		scanf("%lld", &B); B = __gcd(A, B);
		for(i = 1; i <= cnt; ++i)
			if(!(B % p[i])){
				printf("%lld\n", B / p[i]); break;
			}
	}
	return 0;
}

坑

坑1：注意当 $d_i = 1$ 时输出 $-1$。