E. Prefix GCD
假设我们从一个空集合\(b\)开始,不断从\(a\)数组中选择一个元素添加到\(b\)集合的尾部,当把\(a\)数组的元素全部添加到\(b\)中后,得到的\(b\)即为所求的rearrange后的\(a\)。
结论1:
每次选择使得其和当前\(b\)中所有元素的最大公约数最小的那个\(a_i\)加入到\(b\)的末尾,即选择\(a_i\),使得\(gcd(b_1, b_2, ..., b_k, a_i)\)最小(假设当前\(b\)的大小为\(k\)),这样得到的\(b\)是最优的。
证明1:
假设当前的\(b\)集合为:
\(b_1, b_2, ..., b_k\),此\(b\)集合即为正确答案的\(b\)的前\(k\)个元素。
使得\(gcd(b_1, b_2, ..., b_k, a_i)\)取得最小值的a_i是\(A\)。
而正确方案中这个步骤应该选择的\(a_i\)是\(B\)。那么有\(gcd(b_1, b_2, ..., b_k, A) <= gcd(b_1, b_2, ..., b_k, B)\)。
结论2:
可以把正确方案的\(b = \{b_1, b_2, ..., b_k, B\}\)①
替换成:
\(b = \{b_1, b_2, ..., b_k, A, B\}\),这样结果不会变坏。②
证明2:
设\(f = \gcd(a_1) + \gcd(a_1, a_2) + \ldots + \gcd(a_1, a_2, \ldots, a_n)\),
则①的\(f\)为\(gcd(b_1) + gcd(b_1, b_2) + ... + gcd(b_1, b_2, ..., b_k) + gcd(b_1, b_2, ..., b_k, B)\)
②的\(f\)为\(gcd(b_1) + gcd(b_1, b_2) + ..., + gcd(b_1, b_2, ..., b_k) + gcd(b_1, b_2, ..., b_k, A) + gcd(b_1, b_2, ..., A, B)\)
二者不同的部分满足\(gcd(b_1, b_2, ..., b_k, B) >= gcd(b_1, b_2, ..., b_k, A) + gcd(b_1, b_2, ..., b_k, A, B)\),
因为\(gcd(b_1, b_2, ..., b_k, A) + gcd(b_1, b_2, ..., b_k, A, B) = gcd(b_1, b_2, ..., b_k, A) + gcd(b_1, b_2, ..., b_k, b_1, b_2, ..., b_k, A, B) = gcd(b_1, b_2, ..., b_k, A) + gcd(gcd(b_1, b_2, ..., b_k, A), gcd(b_1, b_2, ..., b_k, B)) <= gcd(b_1, b_2, ..., b_k, B)\)。
这用到了两个点:
- \(gcd(X, Y) <= |X - Y|\)
- \(gcd(b_1, b_2, ..., b_k, A) <= gcd(b_1, b_2, ..., b_k, B)\)
因此每次选择使得其和当前\(b\)中所有元素的最大公约数最小的那个\(a_i\)加入到\(b\)的末尾满足题意。
优化
设\(g = gcd(a_1, a_2, ..., a_n)\)
我们可以在开始计算前,将每个\(a_i\)除以\(g\),因为这样处理后,\(gcd(a_1, a_2, ..., a_n) = 1\),这意味着,我们选择一部分\(a_i\)到\(b\)中后,就可以使得\(gcd(b_1, b_2, ..., b_k)\)变为\(1\),
事实上,我们每次选择一个\(a_i\)都会使得\(gcd(b)\)下降,因为如果我们某次选择的\(a_i\)没有使得\(gcd(b)\)下降,则说明\(gcd(b)\)已经下降到了\(1\),可以退出迭代了。
最后我们再把结果乘上\(g\)。
如果不进行这一步操作,则很有可能\(gcd(b)\)永远都到不了1。这样的话我们代码中判断到\(1\)的部分应该改为\(g\)。
时间复杂度
因为每个数最多有\(log_2{x}\)个可能相同的质因数,因此只需要\(log_2{10^5}\)次添加就可以使得\(gcd(b) = 1\)。
int n;
int a[N];
void solve() {
cin >> n;
int gcd_all = 0;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
gcd_all = gcd(gcd_all, a[i]);
}
for (int i = 1; i <= n; i ++) {
a[i] /= gcd_all;
}
int cur = 0, cnt = 0;
int ans = 0;
for (int i = 1; i <= n; i ++) {
int min_v = INF;
for (int j = 1; j <= n; j ++) {
min_v = min(min_v, gcd(cur, a[j]));
}
cur = min_v;
cnt ++;
ans += cur;
if (cur == 1) {
ans += n - cnt;
break;
}
}
ans *= gcd_all;
cout << ans << '\n';
}
标签:...,973,gcd,int,题解,元素,Codeforces,选择,使得
From: https://www.cnblogs.com/lightmon5210/p/18435645