题解 CF1349A 【Orac and LCM】
CYJian
2020-05-13 08:22:37
看到 $\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;
}
```