题目链接

小苯的GCD

题目描述

小苯有一个长度为 的数组 。他想要使得所有 的最大公因子是一个素数。即：，其中 是一个素数。他可以对数组进行任意次操作。

操作定义为：选择两个下标 ，同时执行：，。

约束条件是，操作后要保证 仍然是正数，即不能选择 的元素进行减法操作。

请问他是否有可能在任意次操作内将数组变成符合要求的？如果可以，请输出所有可能的最大公因数。

思路分析

1. 寻找不变量

首先分析题目给出的操作：, 。 我们可以发现这个操作有几个关键的不变量：

  1. 数组元素之和：。每次操作，数组的总和 是不变的。
  2. 每个元素的奇偶性：一个数加上或减去2，其奇偶性不会改变。因此，对于数组中的每一个位置 ， 的值是恒定的。

2. 导出必要条件

我们的目标是让操作后的新数组 满足 ，其中 是一个素数。

  • 根据GCD的性质，如果 是整个数组的GCD，那么数组中的每一个元素 都必须是 的倍数。
  • 既然每个 都是 的倍数，那么它们的和 也必然是 的倍数。
  • 由于数组总和是不变的 ()，所以最终的GCD 必须是初始数组总和 的一个素因子。

这给了我们一个强大的筛选条件：我们只需要检查 的所有素因子，看它们是否可能成为最终的GCD。

3. 分情况讨论候选素数

现在，我们假设 是 的一个素因子，来分析 能否成为最终的GCD。

情况一：
  • 如果最终的GCD是2，那么所有 都必须是偶数。
  • 因为每个元素的奇偶性是不变的，所以这要求初始数组中所有的 必须全部是偶数。
  • 如果初始数组所有数都是偶数，它们的和 也必然是偶数，所以 2 确实是 的一个素因子。
  • 那么，这个条件是否充分呢？是的。如果所有 都是偶数，我们可以通过操作将它们变成 。例如，不断从较大的数 中拿出2，加到较小的数 上，理论上可以将数组的“财富”进行转移，只要总和 足够大（ 即可，而题目条件 且 保证了这一点），就可以构造出 [2, 2, ..., S - 2*(n-1)] 这样的状态，其GCD就是2。
  • 所以，2是可能的GCD，当且仅当初始数组所有元素都是偶数。
情况二： 是一个奇素数
  • 如果最终的GCD是奇素数 ，那么所有 都必须是 的倍数。
  • 结合奇偶性不变量，我们有：对于每个 ， 。
  • 同时， 必须是 的倍数，可以写成 的形式，其中 是正整数。
  • 将这两个条件结合起来：。
  • 因为 是奇素数，。所以上式简化为 。
    • 这意味着，如果 是奇数，那么对应的 也必须是奇数。
    • 如果 是偶数，那么对应的 也必须是偶数。
  • 我们还知道总和不变：，即 ，所以 ，即 。
  • 现在问题转化为：是否存在一组正整数 满足以下两个条件？
    2. 对于所有 ， 且 。
  • 要满足条件2，我们至少需要为每个 分配一个初始值。如果 是奇数， 至少是1。如果 是偶数， 至少是2。
  • 因此， 的最小值是：。
  • 这个最小值可以表示为 (奇数个数) * 1 + (偶数个数) * 2。
  • 所以，一个可行的分配方案存在的充要条件是：。
  • 另外，S/p 和 奇数个数 的奇偶性必须相同，因为 偶数个数 * 2 是偶数。
    • 。

4. 算法步骤

  1. 计算数组总和 和奇数的个数 odd_count。

  2. 对 进行质因数分解，得到所有候选素数 。

  3. 初始化一个空的答案列表 ans。

  4. 检查 ：如果 odd_count == 0（即所有数都是偶数），则将 2 加入 ans。

  5. 检查奇素数 ：遍历 的其他（奇）素因子 ：

    a. 计算目标和 。

    b. 计算所需系数和的下限 min_sum_c = odd_count * 1 + (n - odd_count) * 2。

    c. 检查两个条件：

    i.

    ii.

    d. 如果两个条件都满足，则将 加入 ans。

  6. 对 ans 排序（如果按顺序找素因子则不需要），然后输出。如果 ans 为空，输出 "NO"。

代码

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

using namespace std;

// 分解质因数
vector<long long> get_prime_factors(long long n) {
    vector<long long> factors;
    if (n % 2 == 0) {
        factors.push_back(2);
        while (n % 2 == 0) {
            n /= 2;
        }
    }
    for (long long i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            factors.push_back(i);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 2) {
        factors.push_back(n);
    }
    return factors;
}

void solve() {
    int n;
    cin >> n;
    vector<long long> a(n);
    long long sum = 0;
    int odd_count = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
        if (a[i] % 2 != 0) {
            odd_count++;
        }
    }

    vector<long long> candidates = get_prime_factors(sum);
    vector<long long> result_primes;

    for (long long p : candidates) {
        if (p == 2) {
            if (odd_count == 0) {
                result_primes.push_back(2);
            }
        } else {
            long long target_sum_c = sum / p;
            long long min_sum_c = (long long)odd_count * 1 + (long long)(n - odd_count) * 2;
            if (target_sum_c >= min_sum_c && (target_sum_c % 2 == odd_count % 2)) {
                result_primes.push_back(p);
            }
        }
    }

    sort(result_primes.begin(), result_primes.end());

    if (result_primes.empty()) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
        for (int i = 0; i < result_primes.size(); ++i) {
            cout << result_primes[i] << (i == result_primes.size() - 1 ? "" : " ");
        }
        cout << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static List<Long> getPrimeFactors(long n) {
        List<Long> factors = new ArrayList<>();
        if (n % 2 == 0) {
            factors.add(2L);
            while (n % 2 == 0) {
                n /= 2;
            }
        }
        for (long i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                factors.add(i);
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        if (n > 2) {
            factors.add(n);
        }
        return factors;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        long sum = 0;
        int oddCount = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            sum += a[i];
            if (a[i] % 2 != 0) {
                oddCount++;
            }
        }

        List<Long> candidates = getPrimeFactors(sum);
        List<Long> resultPrimes = new ArrayList<>();

        for (long p : candidates) {
            if (p == 2) {
                if (oddCount == 0) {
                    resultPrimes.add(2L);
                }
            } else {
                long targetSumC = sum / p;
                long minSumC = (long) oddCount * 1 + (long) (n - oddCount) * 2;
                if (targetSumC >= minSumC && (targetSumC % 2 == oddCount % 2)) {
                    resultPrimes.add(p);
                }
            }
        }

        Collections.sort(resultPrimes);

        if (resultPrimes.isEmpty()) {
            System.out.println("NO");
        } else {
            System.out.println("YES");
            for (int i = 0; i < resultPrimes.size(); i++) {
                System.out.print(resultPrimes.get(i) + (i == resultPrimes.size() - 1 ? "" : " "));
            }
            System.out.println();
        }
    }
}

import sys
import math

def get_prime_factors(n):
    factors = set()
    if n % 2 == 0:
        factors.add(2)
        while n % 2 == 0:
            n //= 2
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            factors.add(i)
            while n % i == 0:
                n //= i
    if n > 2:
        factors.add(n)
    return sorted(list(factors))

def solve():
    try:
        n = int(sys.stdin.readline())
        a = list(map(int, sys.stdin.readline().split()))
    except (IOError, ValueError):
        return

    total_sum = sum(a)
    odd_count = sum(1 for x in a if x % 2 != 0)
    
    candidates = get_prime_factors(total_sum)
    result_primes = []
    
    for p in candidates:
        if p == 2:
            if odd_count == 0:
                result_primes.append(2)
        else: # p is an odd prime
            target_sum_c = total_sum // p
            min_sum_c = odd_count * 1 + (n - odd_count) * 2
            
            if target_sum_c >= min_sum_c and target_sum_c % 2 == odd_count % 2:
                result_primes.append(p)
                
    if not result_primes:
        print("NO")
    else:
        print("YES")
        print(*result_primes)

solve()

算法及复杂度

  • 算法：

    1. 不变量分析：核心思想是发现操作不改变数组总和与每个元素的奇偶性。
    2. 条件推导：基于不变量，推导出任何可能的素数GCD 必须是数组总和 的一个素因子。
    3. 可行性判断：
      • 对于 ，要求原数组所有数都是偶数。
      • 对于奇素数 ，需要能够构造出一组合法系数 使得 。这被转化为一个关于系数和与奇偶性的检查。
    4. 实现：先计算总和 ，再对 进行质因数分解，最后逐一验证每个素因子是否满足可行性条件。

  • 时间复杂度：，其中 是数组元素总和， 是数组长度。

    • 计算总和与奇数个数需要 。
    • 对总和 进行质因数分解，时间复杂度为 。
    • 遍历素因子并进行判断的步骤非常快。
    • 因此，总的时间复杂度由质因数分解主导，为 。

  • 空间复杂度： 或 ，主要用于存储 的质因数，其中 是 的不同质因子的数量，这个值通常很小。