- 题意:
- 输入n个正整数和一个k,询问最多有多少个整数相加可以整除k
-
思路:
同余定理,
对于每一个数字,取%k的余数为下标,统计余数的个数 cnt[i]
例如:\[a = n_1k + c_1 \]
\[ b = n_2k + c_2 \]
要使得 \[ a + b \mod k = 0\]
\[(n_1+n_2) k + c_1+c_2 \mod k = 0\]
即
\[ if\quad c_1 + c_2 =0 \quad or \quad c_1 + c_2=k\]code
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,k,t,ans=0;
scanf("%d%d",&n,&k);
vector<int> cnt(k); // 预先申请k个空间
for(int i=0;i<n;++i){
scanf("%d",&t);
cnt[t%k]++;
}
ans += cnt[0]/2;// 余数为0 ,肯定整除k,/2是因为要统计全部之后,再*2
for(int i=1;i<(k+1)/2;++i){
ans += min(cnt[i],cnt[k-i]);// i + (k-i) % k == 0 ,取公共的部分min
}
if(k%2==0) ans+=cnt[k/2]/2; // 如果k是偶数
//由于i<(k+1)/2 ,取不到中间的偶数,即取不到(k/2)这个数字,再判断该数字有多少对,因为 k/2 + k/2 == k;
printf("%d",ans*2);//ans 是对数, * 2 才是个数
return 0;
}