0829-T3 公因数
题意
给定一个长度为 \(n\) 的序列，可以做若干次操作。
每次操作选择两个数 \(A,B\)，选择 \(A\) 的一个质因数 \(P\)，将 \(A\) 变为 \(\frac{A}{P}\)，将 \(B\) 变为 \(BP\)。
求经过若干次操作后序列最大公因数的最大值，以及此情况下操作的最小次数。
思路
每次操作不会改变序列总共的质因数和次数。
想要最大公因数最大，必须让质因数的次数平均分配给每个数。
现将每个数都质因数分解，次数加起来。
容易发现每个质因数的次数 \(c\)，对答案的共献为 \(\lfloor\frac{c}{n}\rfloor\)。
对于操作次数，如果 \(A_i\) 的质因数 \(p_i\) 的次数为 \(c_i\)，并且 \(c_i\) 小于答案中 \(p_i\) 的次数 \(C_i\)，对答案就有贡献。
\(A_i\) 至少会操作 \(C_i-c_i\) 次把外面的质因数 \(p_i\) 收集 回来， 答案加上 \(C_i-c_i\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, a[N], c[N], ans1 = 1, ans2;
int q[N], tot, b[N];
int qpow(int a, int p) {
int res = 1;
for (; p; p >>= 1, a *= a)
if (p & 1) res *= a;
return res;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1, t; i <= n; i ++) {
t = a[i];
for (int j = 2; j * j <= a[i]; j ++) {
if (t % j) continue;
if (!c[j]) q[++ tot] = j;
while (t % j == 0) t /= j, c[j] ++;
}
if (t != 1) {
if (!c[t]) q[++ tot] = t;
c[t] ++;
}
}
for (int i = 1; i <= tot; i ++) c[q[i]] /= n;
for (int i = 1; i <= tot; i ++) ans1 *= qpow(q[i], c[q[i]]);
for (int i = 1, t; i <= n; i ++) {
t = a[i];
for (int j = 2; j * j <= a[i]; j ++) {
if (t % j) continue;
while (t % j == 0) t /= j, b[j] ++;
}
if (t != 1) b[t] ++;
for (int j = 1; j <= tot; j ++) ans2 += max(0, c[q[j]] - b[q[j]]);
t = a[i];
for (int j = 2; j * j <= a[i]; j ++) {
if (t % j) continue;
while (t % j == 0) t /= j, b[j] --;
}
if (t != 1) b[t] --;
}
cout << ans1 << " " << ans2 << "\n";
return 0;
}