非整除集合

//K范围很小啊，直接求余数哈希，特别注意处理一下余数为0，以及K为偶数时余数为K/2的情况即可。
#include<iostream>
using namespace std;

int main() {
    int N, K;
    cin>>N>>K;
    
    int rec[K];
    long long tmp;
    int res = 0;
    
    for(int i = 0; i < K; i++) {
        rec[i] = 0;
    }
        
    for(int i = 0; i < N; i++) {
        cin>>tmp;
        rec[tmp%K]++;
    }
    
    if(rec[0] > 0) {
        res = 1;
    }
    if(K%2 == 0) {
        for(int i = 1; i <= K/2-1; i++) {
            res = res + max(rec[i], rec[K-i]);
        }
        if(rec[K/2] > 0) {
            res++;
        }
    }
    else {
        for(int i = 1; i <= K/2; i++) {
            res = res + max(rec[i], rec[K-i]);
        }
    }
    cout<<res<<endl;
    return 0;
}

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

int main(){
    int n,k,x;
    cin>>n>>k;
    int a[k];
    memset(a,0,sizeof(a));
    for(int i=0;i<n;i++){
        cin>>x;
        a[x%k]++;
    }
    int s = a[0]>0?1:0;
    for(int i=1,j=k-1;i<=j;i++,j--)
        s += (i==j)?(a[i]>0?1:0):max(a[i],a[j]);
    cout<<s<<endl;
    return 0;
}

import java.util.*;
public class Main {
    // 子集合中任意两数之和不能被k整除
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt(), k = in.nextInt();
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextLong();
            }
            fun(arr, k);
        }
    }
    // 动态规划处理
    public static void fun(long[] arr, int k) {
        int n = arr.length;
        Node[] dp = new Node[n];
        for (int i = 0; i < n; i++) { // base case
            dp[i] = new Node();
            if (arr[i] % k != 0) {
                dp[i].size = 1;
                dp[i].list.add(arr[i]);
            }
        }
        int max = 0; // 最大长度
        for (int i = 1; i < n; i++) {
            int idx = -1; // 记录最大下标
            for (int j = 0; j < i; j++) {
                if ((arr[i] + arr[j]) % k != 0) { // 存在
                    boolean flag = true;
                    for (long l : dp[j].list) { // 观察每一个是否可行
                        if ((arr[i] + l) % k == 0) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) { // 都相安无事就更新
                        if (dp[j].size + 1 > dp[i].size) {
                            dp[i].size = dp[j].size + 1;
                            idx = j;
                        }
                    }
                }
            }
            if (idx != -1) { // 找到了可以加入的集合
                dp[i].size = dp[idx].size + 1;
                dp[i].list = dp[idx].list;
                dp[i].list.add(arr[i]);
                max = Math.max(max, dp[i].size);
            }
        }
        System.out.println(max);
    }
}
// 结点的定义
class Node {
    int size;
    ArrayList<Long> list;
    public Node() {
        size = 0;
        list = new ArrayList<>();
    }
}

a=list(map(int,input().split()))
if len(a)<2:
    l=a
    k=int(input())
else:
    l=a[0]
    k=a[1]
arr=list(map(int,input().split()))
arr_1=[i%k for i in arr]
count_n=0
for i in range(0,k):
    if i in arr_1:
        if i==0:
            count_n+=1
        elif i ==k/2:
            count_n+=1
        else:
            num_i=0
            for j in arr_1:
                if j==i:
                    num_i+=1
            if k-i in arr_1:
                num_k_i=0
                for p in arr_1:
                    if p==k-i:
                        num_k_i+=1
                count_n+=max(num_i,num_k_i)
                arr_1.remove(k-i)
            else:
                count_n+=num_i
        arr_1.remove(i)
print(count_n)

package main
import (
	"fmt"
)
/*

1,感觉是这是一个数学问题，和数据结构没什么关系，开始是想用回溯组合求值，但是后来发现了其中的数学规律。
题目说 任意两个数字的和都不能被K整除， 也就是这两个任意数之和 对K模运算取余数 不能整除 K 。这里调一下计算顺序。，先取模，并记录次数。
1.1 将 N个数 对 K 取余 ，将余数和对应出现的次数放入 Map中。
1.2 [0, 1, 2, 3, .... , K-1] 是 Map 中可能存在的键值。将这些键值从中间分为两份，因为 中间堆成，比如 1 和 K-1 不能同时出现，哪一个出现的次数多就取哪一个
1.3 处理边界条件， K 为 偶数， K/2 最多能出现依次， K为奇数，比较 K/2 和 K-K/2 那个次数出现的多。
1.4 还有一个边界条件，0 最多出现一次
*/
var SMap map[int]int
func main(){
	var N,K, t int
	fmt.Scanf("%d",&N)
	fmt.Scanf("%d",&K)
	SMap := make(map[int]int)

	for i:=0;i<N;i++{
		fmt.Scanf("%d",&t)
		SMap[t%K] = SMap[t%K]+1
	}
	sum := 0
	if SMap[0] > 0 { // 边界为 0 的情况，最多只能出现一次
		sum = 1
	}
	for i := 1; i < K/2 ; i++ {
		sum += Max(SMap[i], SMap[K-i]) // 对称比较， i 和 K-i 不能同时现在结果中。
	}
	if K%2 == 0 {  // 边界条件， 处理 K 的奇偶情况
		if SMap[K/2] > 0 { // K/2 = K-K/2
			sum += 1
		}
	} else {
		sum += Max(SMap[K/2], SMap[K-K/2]) // K/2 != K-K/2
	}
	fmt.Println(sum)
}
func Max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

class Solution {
    public:
        long hanWuJi_JiHeYuanSuBuNengZhengchu(vector<int> S, int K)
	{
		for (auto iteri = S.begin(); iteri != S.end(); iteri++)
		{
			for (auto iterj = iteri+1; iterj != S.end(); )
			{
				if ((*iteri + *iterj) % K == 0)
				{
					iterj=S.erase(iterj);
				}
				else iterj++;
			}
		}
		return S.size();
	}
};

## 为啥只能过80%？？？
N, K = list(map(int, input().split()))
nums = list(map(int, input().split()))

arr = [0 for _ in range(K)]
for it in nums:
    arr[it%K] += 1
    
tSum = 0
if arr[0] >= 1:
    tSum = 1

i, j = 1, K-1
while i <= j:
    if i == j and arr[i] >= 1:
        tSum += 1
    else:
        tSum += max(arr[i], arr[j])
    i+=1
    j-=1
    
print(tSum)

#include<iostream>
using namespace std;
int main()
{
	int n,k,a[10001],i,num[101]={0},ke,max=0;
	cin>>n>>k;
	for(i=1;i<=n;i++){cin>>a[i];a[i]=a[i]%k;num[a[i]]++;}//取余数，统计一下
	if(k%2==0){ke=k/2-1;if(num[k/2])max=1;}//k/2是整数的话处理一下
	else ke=k/2;
    if(num[0])max++;//余数为0的只能有一个
	for(i=1;i<=ke;i++)
	if(num[i]>num[k-i])max=max+num[i];
	else max=max+num[k-i];//i和k-i哪个多就加哪个
	cout<<max;
	return 0;
}