题解 | #非整除集合#

题目链接

非整除集合

题目描述

给定一个由正整数组成的集合 S，以及一个整数 K。

需要找出一个最大的子集，使得该子集中任意两个数字的和都不能被 K 整除。输出这个最大子集的元素数量。

解题思路

这个问题的核心在于模运算。一个数 a 加上一个数 b 的和能否被 K 整除，完全取决于它们各自对 K 的余数。

(a + b) % K == 0 等价于 (a % K + b % K) % K == 0。

这启发我们将原问题从处理可能很大的整数，转化为处理 0 到 K-1 范围内的余数。

1. 核心思想：按余数分组

我们可以遍历一次输入集合，用一个频率数组（或哈希表）counts 来统计每个余数（从 0 到 K-1）出现的次数。counts[i] 就表示原集合中有多少个数满足 num % K == i。

2. 构造最大子集的策略

现在，我们的目标是从这些按余数分好的组中挑选数字，以构成满足条件的最大子集。

对于余数为 r1 和 r2 的两组数：如果 (r1 + r2) % K == 0，那么我们不能同时从这两组中各取一个数。
关键配对：满足 (r1 + r2) % K == 0 的余数对主要是 i 和 K-i（其中 1 <= i < K）。

基于此，我们可以制定如下选择策略：

处理余数为 0 的组 (counts[0])：
- 如果取两个余数为 0 的数 a 和 b，它们的和 a+b 的余数也是 0，可以被 K 整除。
- 因此，我们最多只能从 counts[0] 这组数中选择一个。
- 如果 counts[0] > 0，我们的答案中可以包含1个这样的数。
处理成对的余数组 (counts[i] 和 counts[K-i])：
- 对于 1 <= i < K/2 的每个 i，余数 i 和余数 K-i 是成对的。
- 如果同时选取一个余数为 i 的数和一个余数为 K-i 的数，它们的和可以被 K 整除。
- 所以，对于 counts[i] 和 counts[K-i] 这两组数，我们只能选择其中一组加入最终的子集。为了让子集最大化，我们应该选择数量较多的那一组。
- 因此，对每一对 (i, K-i)，我们向答案贡献 max(counts[i], counts[K-i])。
处理特殊余数 K/2 (当 K 为偶数时)：
- 如果 K 是偶数，那么 i = K/2 是一个特殊的余数，因为它自己和自己配对：(K/2 + K/2) % K = K % K = 0。
- 这和余数为 0 的情况类似，我们最多只能从 counts[K/2] 这组数中选择一个。
- 如果 K 是偶数且 counts[K/2] > 0，我们的答案中可以再包含1个这样的数。

算法步骤总结

创建一个大小为 K 的频率数组 counts。
遍历输入集合，用 counts 统计每个数模 K 的余数的出现次数。
初始化最终子集大小 max_size = 0。
如果 counts[0] > 0，max_size 增加 1。
循环 i 从 1 到 (K-1)/2，对于每一对 (i, K-i)，将 max(counts[i], counts[K-i]) 加到 max_size 上。
如果 K 是偶数且 counts[K/2] > 0，max_size 再增加 1。
返回 max_size。

代码

c++
java
python

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

using namespace std;

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

    int n, k;
    cin >> n >> k;

    vector<int> counts(k, 0);
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        counts[val % k]++;
    }

    int max_size = 0;

    // Case 1: Remainder 0
    if (counts[0] > 0) {
        max_size = 1;
    }

    // Case 2: Remainder pairs (i, k-i)
    for (int i = 1; i <= k / 2; ++i) {
        if (i != k - i) { // Not the middle element for even K
            max_size += max(counts[i], counts[k - i]);
        }
    }

    // Case 3: Remainder k/2 for even K
    if (k % 2 == 0 && counts[k / 2] > 0) {
        max_size++;
    }

    cout << max_size << endl;

    return 0;
}

import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;

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

        int[] counts = new int[k];
        for (int i = 0; i < n; i++) {
            int val = sc.nextInt();
            counts[val % k]++;
        }

        int maxSize = 0;
        
        // Case 1: Remainder 0
        if (counts[0] > 0) {
            maxSize = 1;
        }

        // Case 2: Remainder pairs (i, k-i)
        for (int i = 1; i <= k / 2; i++) {
            if (i != k - i) {
                maxSize += Math.max(counts[i], counts[k - i]);
            }
        }

        // Case 3: Remainder k/2 for even K
        if (k % 2 == 0 && counts[k / 2] > 0) {
            maxSize++;
        }

        System.out.println(maxSize);
    }
}

import sys

def solve():
    try:
        line1 = sys.stdin.readline()
        if not line1:
            return
        n, k = map(int, line1.split())
        
        a = list(map(int, sys.stdin.readline().split()))
        
        counts = [0] * k
        for x in a:
            counts[x % k] += 1
            
        max_size = 0
        
        # Case 1: Remainder 0
        if counts[0] > 0:
            max_size = 1
            
        # Case 2: Remainder pairs (i, k-i)
        for i in range(1, (k // 2) + 1):
            if i != k - i:
                max_size += max(counts[i], counts[k-i])

        # Case 3: Remainder k/2 for even K
        if k % 2 == 0 and counts[k//2] > 0:
            max_size += 1
            
        print(max_size)

    except (IOError, ValueError):
        return

solve()

算法及复杂度

算法：数论、模运算、贪心
时间复杂度: $\mathcal{O}(N + K)$ 。其中 $\mathcal{O}(N)$ 用于遍历输入数组并计算余数频率， $\mathcal{O}(K)$ 用于遍历频率数组以构建最大子集。
空间复杂度: $\mathcal{O}(K)$ ，用于存储余数频率的数组。