CF2148G 题解

深圳信奥算法部-吴传民

2026-01-30 15:09:31

发布于：广东

21阅读

0回复

0点赞

CodeForces 2148G Farmer John's Last Wish 题解

原题链接：https://codeforces.com/problemset/problem/2148/G

一、题目大意

给你一个数组前缀： $[a_1,a_2,\dots,a_i]$ 。

你可以随便重新排列这 $i$ 个数。

我们定义：

从左到右看前缀的 gcd（最大公约数）会越来越小或不变。
如果在某个位置 $k$ ：
$\gcd(a_1,\dots,a_k) > \gcd(a_1,\dots,a_{k+1})$
说明在加上第 $k+1$ 个数时，gcd 真的变小了。

题目要你对每个前缀，求出：
通过最好的重排，能让“最后一次 gcd 变小”发生得尽量靠后，也就是最大的 $k$ 。

输出每个前缀的答案。

二、思考方向

想让“最后一次 gcd 下降”尽量靠后，意味着：

前面尽量多放一些“很合得来”的数（gcd 不会被破坏）。
直到最后某一步，放一个“不合群”的数，gcd 才下降。

所以我们只需要考虑两种“答案的产生方式”：

情况 A：新来的数当“破坏者”

如果当前前缀整体 gcd 在加入新数后变小了，那么说明：

你可以把新数放到最后
前面 $i-1$ 个先摆好让 gcd 不变
最后这个数一放进去，gcd 降低

因此答案至少可以是：i-1

情况 B：新来的数当“合群者”

如果我们希望最后一次下降发生在更后面，那前面这段必须有 gcd = 某个 $d$ （ $d>1$ ），并且：

前面这段里所有数都能被 $d$ 整除（它们“合群”）
但整个前缀里至少有一个数不能被 $d$ 整除（这样 gcd 才能在后面被“破坏”）

所以对于每个可能的 $d$ （它必须是某些数的因数），我们只要数：

当前前缀中，有多少个数是 $d$ 的倍数（记作 cnt[d]）
如果 cnt[d] != i（不是所有数都能被 $d$ 整除），那就说明可以安排：
- 先放这 cnt[d] 个倍数（前缀 gcd 至少是 $d$ ）
- 再放一个不是倍数的数（gcd 会下降）
- 所以答案可以取 cnt[d]

最终每个前缀答案就是：

max( i-1（情况A）, 所有可行的 cnt[d]（情况B） )

三、解题思路

我们从左到右处理前缀。

维护：

nowgcd：当前前缀的整体 gcd
f[d]：当前前缀里，有多少个数能被 $d$ 整除（即 $d$ 的倍数个数）
ans：当前前缀的答案

处理第 $i$ 个数 x：

1）更新所有因数的计数

枚举 x 的所有因数 d：

f[d]++
如果 f[d] != i说明前缀里还有别的数不是 d 的倍数
- 那么 d 是可行的 gcd 候选
- 更新 ans = max(ans, f[d])

2）检查“破坏者”情况

如果 gcd(nowgcd, x) 变小了（不等于 nowgcd）：

说明 x 可以作为最后的破坏者
更新 ans = max(ans, i-1)

3）输出答案，更新 nowgcd

输出 ans
nowgcd = gcd(nowgcd, x)

因数怎么快速枚举？

提前预处理 yin[v]：存 v 的所有因数。
用类似筛法：对每个 i，把它加到所有倍数 j 的因数表里。

复杂度大概是 $O(n \log n)$ ，能过。

四、完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
vector<int> divs[N + 1]; // divs[x] 存 x 的所有因数
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // 预处理每个数的因数表
    for (int d = 1; d <= N; d++)
        for (int x = d; x <= N; x += d)
            divs[x].push_back(d);
    int t;
    cin >> t;
    while (t--) {
        int n, nowgcd = 0, ans = 0;;
        cin >> n;
        vector<int> f(N + 1); // f[d] = 当前前缀里 d 的倍数个数
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            // 情况B：x 作为“合群者”，更新因数计数
            for (int d : divs[x]) {
                f[d]++;
                if (f[d] != i)             // 不是所有数都是 d 的倍数
                    ans = max(ans, f[d]);  // 可以先放这 f[d] 个倍数
            }
            // 情况A：x 作为“破坏者”
            int newg = gcd(nowgcd, x);
            if (newg != nowgcd)         // gcd 发生下降
                ans = max(ans, i - 1);
            cout << ans << ' ';
            nowgcd = newg;
        }
        cout << '\n';
    }
    return 0;
}