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;
}