题解 | #xgcd#_牛客博客

题目链接

小红的数组变换 (注：链接题目操作为 a[j] -> a[i] * a[j]，但奇偶性逻辑与本题 lcm 操作完全相同)

题目描述

小红有一个长度为 $n$ 的数组 $a$ 。她每次可以选定任意的 $i, j(1 \le i, j \le n)$ ，然后同时执行以下两个操作：

$a_i \rightarrow a_i \times a_j$
$a_j \rightarrow \operatorname{lcm}(a_i, a_j)$

小红想知道，把整个数组变成全部都是偶数元素的最少操作次数是多少。若始终无法达成目标，则输出 -1。

思路分析

本题的关键在于分析单次操作对数组中元素奇偶性的影响。我们的目标是将所有奇数变为偶数。

操作的奇偶性分析

设 O 代表奇数，E 代表偶数。操作为 $a_i' = a_i \cdot a_j$ 和 $a_j' = \operatorname{lcm}(a_i, a_j)$ 。我们分析不同奇偶性组合的输入会产生怎样的输出：

操作 (奇数, 奇数):
- $a_i' = O \cdot O = O$
- $a_j' = \operatorname{lcm}(O, O) = O$ (两个奇数的最小公倍数必然是奇数)
- 结果：(O, O) -> (O, O)。奇数个数不变。
操作 (奇数, 偶数):
- $a_i' = O \cdot E = E$
- $a_j' = \operatorname{lcm}(O, E) = E$ (一个奇数和一个偶数的最小公倍数必然是偶数)
- 结果：(O, E) -> (E, E)。一个奇数被成功转化为了偶数，偶数依然是偶数。奇数个数减一。
操作 (偶数, 偶数):
- $a_i' = E \cdot E = E$
- $a_j' = \operatorname{lcm}(E, E) = E$ (两个偶数的最小公倍数必然是偶数)
- 结果：(E, E) -> (E, E)。奇数个数不变。

核心结论

可行性: 要将奇数变为偶数，必须让它和一个偶数进行操作。这意味着，如果数组中一开始没有任何偶数，我们永远无法创造出第一个偶数（因为 (O, O) -> (O, O)），所以目标无法达成。因此，如果数组中全是奇数，应输出 -1。
最少操作次数: 如果数组中至少存在一个偶数，我们就有了一个“偶数源”。对于每一个奇数，我们都可以用这个偶数源（或者操作过程中产生的新的偶数）来和它进行一次操作，将其变为偶数。根据分析，一次 (奇数, 偶数) 操作可以将一个奇数变为偶数，而原有的偶数保持偶数。这个操作精确地将奇数的数量减一。因此，要消除全部 $k$ 个奇数，就需要进行 $k$ 次这样的操作。

算法流程

遍历数组，统计其中奇数的个数，记为 num_odd。
如果 num_odd 等于数组长度 $n$ (即全是奇数)，则输出 -1。
否则（只要至少有一个偶数），最少操作次数就是奇数的个数，输出 num_odd。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    int odd_count = 0;
    bool has_even = false;

    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        if (val % 2 != 0) {
            odd_count++;
        } else {
            has_even = true;
        }
    }

    if (!has_even && n > 0) { // All are odd
        cout << -1 << endl;
    } else {
        cout << odd_count << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int oddCount = 0;
        boolean hasEven = false;

        for (int i = 0; i < n; i++) {
            int val = sc.nextInt();
            if (val % 2 != 0) {
                oddCount++;
            } else {
                hasEven = true;
            }
        }

        if (!hasEven && n > 0) { // All are odd
            System.out.println(-1);
        } else {
            System.out.println(oddCount);
        }
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))

    odd_count = 0
    has_even = False

    for x in a:
        if x % 2 != 0:
            odd_count += 1
        else:
            has_even = True
    
    if not has_even and n > 0:
        print(-1)
    else:
        print(odd_count)

solve()

算法及复杂度

算法：计数
时间复杂度： $O(n)$ ，我们只需要遍历一次数组来统计奇数的个数。
空间复杂度： $O(n)$ 用于存储数组，如果边读边处理则为 $O(1)$ 。