C. Orac and LCM

题意

给出长度为 $n$ 的数组，求 $gcd(lcm(a_i, a_j), i<j)$。

思路

患有质数恐惧症的我又不会做了。其实主要还是因为没有想到点子上。

每一个数都可以质因数分解为 $p_1^ap_2^b \dots$ 这样的形式，我们考虑单个质因子 $p_i$ 。假设有两个数分别有因子 $p_i^{m_1}$ 与 $p_i^{m_2}$ 。当我们求GCD的时候，实际上对于该质因子来说，它的贡献是 $p_i^{\min\{m_1, m_2\}}$ ；当我们求LCM的时候，实际上对于该质因子来说，它的贡献是 $p_i^{\max\{m_1, m_2\}}$ 。

所以综上，对于单个质因子 $p_i$，题目其实就是要求 $\min\{\max\{m_1, m_2\}, \max\{m_1, m_3\}, \dots, \max\{m_1, m_n\} \}$。思考一下就可以发现，就是要求每个质因子 $p_i$ 的第二大指数，也就是 $m_1 \dots m_n$ 的第二大数。

对于每一个数质因数分解，并计算每个质因数的个数。对于每个质数，用一个vector记录出现过的指数。排序，因为 $0$ 的情况不会被放入vector，所以分情况处理。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
vector<int> mp[MAXM];

LL quickPow(LL a, LL b) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

void toPrime(int x) {
    for(int k=2; k*k<=x; k++) {
        if(x % k == 0) {
            int cnt = 0;
            while(x % k == 0) {
                cnt++;
                x /= k;
            }
            mp[k].push_back(cnt);
        }
    }
    if(x > 1) mp[x].push_back(1);
}

int main() {
    // freopen("in.txt", "r", stdin);
    int n; scanf("%d", &n);
    for(int i=0; i<n; i++) mp[i].clear();
    int m = 0;
    for(int i=0; i<n; i++) {
        int x; scanf("%d", &x);
        m = max(m, x);
        toPrime(x);
    }
    LL ans = 1;
    for(int k=2; k<=m; k++) {
        sort(mp[k].begin(), mp[k].end());
        if(mp[k].size() <= n - 2) continue;
        else if(mp[k].size() == n - 1) ans *= quickPow(k, mp[k][0]);
        else ans *= quickPow(k, mp[k][1]);
    }
    printf("%lld\n", ans);
    
    return 0;
}