D. Split Plus K 题解

问题描述

黑板上有 $n$ 个正整数 $a_1, a_2, \dots, a_n$，给定正整数 $k$。每次操作：选择一个数 $x$，擦掉它，写上两个正整数 $y, z$ 满足 $y+z = x + k$。问能否通过若干次操作使得所有数相等，并求出最少操作次数。

---

关键变换

令 $x' = x - k$，将原问题中的每个数都减去 $k$。
原操作 $y+z = x+k$ 变为：

$$(y'+k)+(z'+k) = (x'+k)+k \;\Longrightarrow\; y' + z' = x'. $$

于是变换后的问题等价于：
初始有 $n$ 个数 $a_i' = a_i - k$，每次操作选择一个数 $x'$，擦掉它，写上两个数 $y', z'$ 满足 $y'+z' = x'$。
目标：使所有数相等（记为 $m'$），且原数 $m = m'+k$ 必须为正整数。
操作次数 = 最终数的个数 - 初始个数 $n$。

---

数学模型

设最终所有数变为 $m$（原问题），对应 $m' = m - k$。
对初始的 $a_i$，设它经过 $p_i$ 次操作后变成 $p_i+1$ 个 $m$。每次操作总和增加 $k$，因此：

$$a_i + p_i k = (p_i+1) m.$$

令 $d = m - k$，则 $m = d + k$，代入得：

$$a_i - k = (p_i+1) d \;\Longrightarrow\; a_i' = q_i d, $$

其中 $q_i = p_i+1$ 为正整数。
最终数的总个数为 $\sum q_i = \sum \frac{a_i'}{d}$，初始有 $n$ 个数，所以操作次数为：

$$\text{ans} = \sum_{i=1}^n \frac{a_i'}{d} - n.$$

这里 $d$ 必须整除每一个 $a_i'$，且 $d \neq 0$（若 $d=0$ 则所有 $a_i'=0$，单独处理）。
同时 $m = d+k > 0$ 必须成立，即 $d > -k$。由于 $k \ge 1$，当 $d$ 为负数且绝对值很大时可能破坏正性，但下面将证明只需考虑 $d$ 与 $a_i'$ 同号的情况。

---

可行性分析

• 若所有 $a_i' = 0$，即所有 $a_i = k$，则已经全等，答案为 $0$。
• 否则，$d$ 必须非零。由于 $a_i' = q_i d$，所有 $a_i'$ 必须同号（全正或全负），否则不可能同时被同一个非零 $d$ 整除且 $q_i$ 为正整数。
• 若存在某个 $a_i' = 0$ 而其他非零，则 $0 = q_i d$ 要求 $d=0$ 或 $q_i=0$，前者矛盾，后者不可能（$q_i\ge1$），因此无解。

所以可行当且仅当：

• 所有 $a_i'$ 全为正，或全为负，且没有零。

---

最小化操作次数

当所有 $a_i'$ 同号时，取 $d$ 为它们的最大公因数（带符号）能使 $\sum a_i'/d$ 最小（因为 $d$ 越大，每个商越小）。
设 $g = \gcd(|a_1'|, |a_2'|, \dots, |a_n'|)$，则：

• 若所有 $a_i' > 0$，取 $d = g$；
• 若所有 $a_i' < 0$，取 $d = -g$（此时 $a_i'/d = |a_i'|/g$ 为正整数）。

此时操作次数为：

$$\text{ans} = \sum_{i=1}^n \frac{|a_i'|}{g} - n.$$

注意当所有 $a_i$ 已经相等（且不等于 $k$）时，$a_i'$ 全相等非零，$g = |a_i'|$，代入得 $\text{ans}=n - n = 0$，符合预期。

---

正确性补充说明

• 当 $a_i' > 0$ 时，$d = g > 0$，则最终数 $m = d + k > k \ge 1$，且每次分裂得到的 $y,z$ 在原问题中为 $y'+k, z'+k$，因为 $y',z' > 0$，所以 $y,z > k \ge 1$，均为正整数，符合要求。
• 当 $a_i' < 0$ 时，$d = -g < 0$，则 $m = d + k = k - g$。由于 $a_i' = a_i - k < 0$，故 $a_i < k$，而 $g$ 整除 $|a_i'|$，可能使 $m$ 很小甚至非正？实际上，由 $a_i' = q_i d$，$d<0$，$q_i>0$，得 $a_i' \le d < 0$，故 $|a_i'| \ge |d| = g$，所以 $m = k - g \ge k - |a_i'| \ge k - (k - a_i) = a_i > 0$，因此 $m$ 仍为正整数。同时分裂出的 $y,z$ 在原问题中为 $y'+k, z'+k$，由于 $y',z' > 0$，故 $y,z > k$，而 $a_i < k$，所以新写的数比原来的大，但仍是正整数，符合操作要求。

---

算法步骤

1. 读入 $n, k$ 和数组 $a$。
2. 计算 $b_i = a_i - k$。
3. 若所有 $b_i = 0$，输出 $0$。
4. 若存在 $b_i = 0$ 或 $b_i$ 有正有负，输出 $-1$。
5. 否则，计算 $g = \gcd(|b_1|, |b_2|, \dots, |b_n|)$。
6. 输出 $\left(\sum_{i=1}^n \frac{|b_i|}{g}\right) - n$。

复杂度 $O(n + \log \max a_i)$，满足题目限制。

---

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll gcd(ll a, ll b) {
    while (b) { ll t = b; b = a % b; a = t; }
    return a;
}

void solve() {
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    vector<ll> b(n);
    for (int i = 0; i < n; ++i) b[i] = a[i] - k;

    // 检查是否全零
    bool all_zero = true;
    for (ll x : b) if (x != 0) { all_zero = false; break; }
    if (all_zero) {
        cout << "0\n";
        return;
    }

    // 检查是否有零或异号
    bool has_zero = false;
    bool pos = false, neg = false;
    for (ll x : b) {
        if (x == 0) has_zero = true;
        else if (x > 0) pos = true;
        else neg = true;
    }
    if (has_zero || (pos && neg)) {
        cout << "-1\n";
        return;
    }

    // 计算 gcd 绝对值
    ll g = 0;
    for (ll x : b) {
        g = gcd(g, abs(x));
    }

    ll total = 0;
    for (ll x : b) {
        total += abs(x) / g;
    }
    cout << total - n << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

---

样例验证

输入：

9
2 1
3 4
2 3
7 11
3 10
100 40 100
2 1
1 2
2 2
1 2
1 327869541
327869541
5 26250314066
439986238782 581370817372 409476934981 287439719777 737637983182
5 616753575719
321037808624 222034505841 214063039282 441536506916 464097941819
5 431813672576
393004301966 405902283416 900951084746 672201172466 518769038906

输出：

3
1
4
-1
-1
0
3119
28999960732
-1

与题目要求一致。

---

总结

本题通过变换 $x' = x - k$ 将操作转化为简单的分裂（和不变），然后利用整除性和最大公因数求解。关键在于判断所有 $a_i - k$ 必须同号且非零，此时最优的最终值由它们的最大公因数决定。最终操作次数即为总份数减去初始个数。