UOJ48 【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 进行输入输出。

数据范围：

$n \le 10^5,a_i \le 10^{12}$

~~啥？我就用cin/cout你打我啊？？~~

首先很容易想到，这个 $\text{sgcd}(a,b)$ 其实就是 $\gcd(a,b)$ 去除以它的最小素因子。

这就是暴力解法。把 $10^6$ 以内的所有素数都筛出来，然后暴力找 $\gcd(a_1,a_i)$ 的最小素因子

时间复杂度 $O\left(\frac{M}{\ln M} + n\frac{\sqrt{a_i}}{\ln a_i}\right),M=10^6$ ，显然过不了这题。

注：这里的复杂度其实是利用了「不超过 $x$ 的素数有 $O\left(\frac{x}{\ln x}\right)$ 个」这个性质分析的。

考虑优化这个暴力

注意到这个最小素因子一定是 $a_1$ 的质因子

然后我们预处理 $a_1$ 的质因子就好了

时间复杂度 $O(\sqrt{a_1} + n \log a_1)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)())

int n,cnt;
int A,B,p[55];
int gcd(int a,int b) {return b==0 ? a : gcd(b,a%b);}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> A; B=A;
    for(int i=2; i*i <= B; i++)
        if(B%i==0) for(p[++cnt] = i; B%i==0; B/=i);
    if(B>1) p[++cnt] = B; p[++cnt]=-1;
    cout << (A / p[1]) << ' ';
    while(--n)
    {
        cin >> B; B = gcd(A,B);
        for(int i=1; i<=cnt; i++)
            if(B%p[i] == 0) {cout << (B / p[i]) << " \n"[n==1]; break;}
    }
    return 0;
}