小苯的GCD

[题目链接](https://www.nowcoder.com/practice/d60255d102394b299a1b8ddd423d6edc)

思路

操作分析

每次操作选择两个下标 $i, j$ ，令 $a_i = a_i + 2$ ， $a_j = a_j - 2$ （需 $a_j > 2$ ）。

两个关键不变量：

数组总和 $S$ 不变：一次操作加减抵消。
每个元素的奇偶性不变：加减 2 不改变奇偶。

必要条件

若最终 $\gcd = p$ （素数），则 $p \mid a_i$ 对所有 $i$ 成立，从而 $p \mid S$ 。因此 $p$ 必须是 $S$ 的质因子。

p = 2 的情况

每个元素必须是偶数。由于奇偶性不变，所有元素初始就必须是偶数。

若全部为偶数，最小分配是每个元素 $2$ ，剩余 $S - 2n$ 以 $4$ （即 $2p$ ）为单位分配（保持偶数性），所以需要 $S - 2n \geq 0$ 且 $(S - 2n) \bmod 4 = 0$ 。

p 为奇素数的情况

对于奇素数 $p$ ， $\gcd(2, p) = 1$ ，因此通过反复 $+2$ 或 $-2$ ，可以将任何元素的 $\bmod\; p$ 余数调为 $0$ 。但要保证分配方案满足奇偶性约束：

奇数元素 $\to$ 奇数倍的 $p$ ，最小为 $p$ 。
偶数元素 $\to$ 偶数倍的 $p$ ，最小为 $2p$ 。

设奇数个数为 $c_{\text{odd}}$ ，偶数个数为 $c_{\text{even}}$ 。最小所需总和为：

$ $p \cdot c_{\text{odd}} + 2p \cdot c_{\text{even}}$ $

剩余量 $R = S - p \cdot c_{\text{odd}} - 2p \cdot c_{\text{even}}$ 只能以 $2p$ 为单位分配给各元素（给任一元素加 $2p$ 不改变其奇偶性），因此需要 $R \geq 0$ 且 $R \bmod 2p = 0$ 。

算法步骤

计算 $S = \sum a_i$ ，统计奇数个数 $c_{\text{odd}}$ 。
对 $S$ 质因数分解，枚举每个质因子 $p$ 。
根据 $p$ 是否为 2 分别检查上述条件。
将所有合法的 $p$ 排序输出。

复杂度

时间复杂度： $O(n + \sqrt{S})$ ，其中 $S \leq 2 \times 10^{11}$ ， $\sqrt{S} \approx 4.5 \times 10^5$ 。
空间复杂度： $O(1)$ （不计输入）。

代码

C++
Java

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    long long S = 0;
    int count_odd = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        S += x;
        if (x % 2 == 1) count_odd++;
    }
    int count_even = n - count_odd;

    // 质因数分解 S
    vector<long long> primes;
    long long tmp = S;
    for (long long d = 2; d * d <= tmp; d++) {
        if (tmp % d == 0) {
            primes.push_back(d);
            while (tmp % d == 0) tmp /= d;
        }
    }
    if (tmp > 1) primes.push_back(tmp);

    vector<long long> result;
    for (long long p : primes) {
        if (p == 2) {
            if (count_odd == 0) {
                long long surplus = S - 2LL * n;
                if (surplus >= 0 && surplus % 4 == 0) {
                    result.push_back(2);
                }
            }
        } else {
            long long min_sum = p * count_odd + 2LL * p * count_even;
            long long surplus = S - min_sum;
            if (surplus >= 0 && surplus % (2 * p) == 0) {
                result.push_back(p);
            }
        }
    }

    sort(result.begin(), result.end());
    if (result.empty()) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
        for (int i = 0; i < (int)result.size(); i++) {
            if (i > 0) cout << " ";
            cout << result[i];
        }
        cout << endl;
    }

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        long S = 0;
        int countOdd = 0;
        for (int i = 0; i < n; i++) {
            long x = in.nextLong();
            S += x;
            if (x % 2 == 1) countOdd++;
        }
        int countEven = n - countOdd;

        List<Long> primes = new ArrayList<>();
        long tmp = S;
        for (long d = 2; d * d <= tmp; d++) {
            if (tmp % d == 0) {
                primes.add(d);
                while (tmp % d == 0) tmp /= d;
            }
        }
        if (tmp > 1) primes.add(tmp);

        List<Long> result = new ArrayList<>();
        for (long p : primes) {
            if (p == 2) {
                if (countOdd == 0) {
                    long surplus = S - 2L * n;
                    if (surplus >= 0 && surplus % 4 == 0) {
                        result.add(2L);
                    }
                }
            } else {
                long minSum = p * countOdd + 2L * p * countEven;
                long surplus = S - minSum;
                if (surplus >= 0 && surplus % (2 * p) == 0) {
                    result.add(p);
                }
            }
        }

        Collections.sort(result);
        if (result.isEmpty()) {
            System.out.println("NO");
        } else {
            System.out.println("YES");
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < result.size(); i++) {
                if (i > 0) sb.append(" ");
                sb.append(result.get(i));
            }
            System.out.println(sb.toString());
        }
    }
}

题解 | #小苯的GCD#