-
原题链接
-
测试样例
input
4
6 4
2 2 8 6 9 4
10 8
1 1 1 5 2 4 4 8 6 7
1 1
666
2 2
2 4
output
3
6
1
1 -
Note
In the first test case we can divide the elements as follows:
[ 4 , 8 ] [4,8] [4,8]. It is a 4-divisible array because 4 + 8 4+8 4+8 is divisible by 4 4 4.
[ 2 , 6 , 2 ] [2,6,2] [2,6,2]. It is a 4-divisible array because 2 + 6 2+6 2+6 and 6 + 2 6+2 6+2 are divisible by 4.
[ 9 ] [9] [9]. It is a 4-divisible array because it consists of one element. -
解题思路
在这之前,我们再来解释一下题目吧,给定我们一个长度为 n n n的数组 a a a,我们需要将这数组分成好几个数组,其中对于长度大于 1 1 1的数组,都必须满足相邻元素相加能够整除 m m m,我们的任务就是计算我们最小能分成几个数组。实际上这就是一个凑 m m m的题,我们只关心数组中的元素对 m m m的余数,所以我们可以用哈希表将余数都存起来,那么接下来我们怎么最优的分数组呢?就是这样分: x , m − x , x , m − x , x . . . . x,m-x,x,m-x,x.... x,m−x,x,m−x,x....,那么这样必须满足什么条件,我们发现这对互余数它们的数量之差最多为 1 1 1,而对于大于 1 1 1的我们无法分配这么多,那么其余的就要单独开数组分了。 我们按照这样的思路,就可以解题了,遍历我们存储好的余数,统计即可。 - 代码
/**
* @filename:B.cbp
* @Author : pursuit
* @Blog:unique_pursuit
* @email: 2825841950@qq.com
* @Date : 2021-03-17-22.55.57
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn=1e5+5;
const int mod=1e9+7;
int t,n,m;
map<int,int> p;
void solve(){
int ans=0;
if(p[0]){
//如果存在,就将这些分为一组。
ans++;
}
for(int i=1;i<m;i++){
if(p[i]){
//那么我们就需要去寻找它们的互余数数量。
if(abs(p[i]-p[m-i])<=1){
//要知道我们构造只能夹着凑,即两个互余数数量之差最多为1.
ans++;
}
else{
//说明互余数不足,我们需要额外分一数组。
ans+=abs(p[i]-p[m-i]);
}
p[m-i]=0;//避免重复计算。
}
}
cout<<ans<<endl;
}
int main(){
while(cin>>t){
while(t--){
cin>>n>>m;
p.clear();
vector<int> a(n);
for(int i=0;i<n;i++){
cin>>a[i];
//记录余数,因为我们只关心能否整除m,对m取余能有效处理,将范围都变成m以内。
p[a[i]%m]++;
}
solve();
}
}
return 0;
}