题解 CF1349A 【Orac and LCM】

CYJian

2020-05-13 08:22:37

Solution

看到 $\gcd$ 和 $\mathrm{lcm}$,应该立马想到对每个质因数计算贡献。(当然不是所有题都这样,但是这个很常用) 然后考虑对于一个质数 $p$ 对答案的贡献,这个先 $\rm lcm$ 再 $\gcd$ 是在干啥事情: 任取两个数的 $\rm lcm$,等价于取 $p$ 的指数 $\max$,然后再对所有的 $\rm lcm$ 取 $\gcd$,等价于对每一对 $a_i$ 的 $p$ 的指数 $\max$ 取个 $\min$。 那,$\gcd$ 里头 $p$ 的指数,不就是所有数中 $p$ 的第二大的指数嘛! 分解一下质因数,就做完了。 使用欧拉筛处理出每个数的最小质因子,复杂度 $O(n \log a_{mx})$。 $\rm Code$: ```cpp const int MAXN = 300010; int f[MAXN]; int g[MAXN]; int tot; int pri[MAXN]; int chk[MAXN]; int Min[MAXN]; inline void Sieve(int n) { for(int i = 2; i <= n; i++) { if(!chk[i]) pri[++tot] = i, Min[i] = i; for(int j = 1; j <= tot; j++) { if(i * pri[j] > n) break; chk[i * pri[j]] = 1; Min[i * pri[j]] = pri[j]; if(i % pri[j] == 0) break; } } } vector<int>d[MAXN]; int main() { Sieve(200000); int n = ri; for(int i = 1; i <= n; i++) { int x = ri; while(x > 1) { int p = Min[x], ct = 0; while(x % p == 0) x /= p, ++ct; d[p].push_back(ct); } } ll res = 1; for(int i = 1; i <= 200000; i++) { if(d[i].size() >= n - 1) { sort(d[i].begin(), d[i].end()); int pw = d[i][0]; if(d[i].size() == n) pw = d[i][1]; while(pw--) res *= i; } } cout << res << endl; return 0; } ```