题目描述
给出一个长度为 $n$ 的数列 $a$ ，求 $a_1$ 分别与 $a_1...a_n$ 的次大公约数。不存在则输出-1。
输入
第一行一个正整数 $n$ 。
第二行 $n$ 个用空格隔开的正整数，第 $i$ 个为 $a_i$ 。
$n\le 10^5,a_i\le 10^{12}$
输出
一行 $n$ 个用空格隔开的整数，第 $i$ 个表示 $\text{sgcd}(a_1,a_i)$ 。
样例输入
4
12450 1 2 450
样例输出
6225 -1 1 75
题解
数论
次大公约数显然是最大公约数除以它的最小质因子得到的结果。
但是每次都求最大公约数，然后再找最小质因子的话，时间复杂度为 $O(n\sqrt a)$ ，无法承受。
考虑：每次都是用 $a_1$ 与其它数求次大公约数，而最大公约数的因子一定是两个数的因子。
因此可以直接预处理出 $a_1$ 的所有质因子，然后每次枚举判断是否成立即可。
由于质因子只有 $O(\log a)$ 个，因此时间复杂度为 $O(\sqrt a+n\log a)$
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a[100010] , v[40];
inline ll gcd(ll a , ll b)
{
ll t;
while(b) t = a , a = b , b = t % b;
return a;
}
int main()
{
int n , m = 0 , i , j;
ll t;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%lld" , &a[i]);
for(i = 2 , t = a[1] ; 1ll * i * i <= t ; i ++ )
{
if(!(t % i))
{
v[++m] = i;
while(!(t % i)) t /= i;
}
}
if(t != 1) v[++m] = t;
for(i = 1 ; i <= n ; i ++ )
{
t = gcd(a[1] , a[i]);
for(j = 1 ; j <= m ; j ++ )
{
if(!(t % v[j]))
{
printf("%lld " , t / v[j]);
break;
}
}
if(j > m) printf("-1 ");
}
return 0;
}