题解：CF1374D Zero Remainder Array

Gartjock · 2025-10-31 09:04:48 · 题解

思路

我们处理每个数需要增加的值，对于每个相邻的值判断是否冲突，处理掉冲突之后最大需要增加的值就是答案了，在此基础上要注意开始时 x 为 0 要加上这次增加操作。

代码

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e6+6,inf=2e18;
typedef pair<int,int>PII;
vector<int>v;
int n,a[N],c,k,T,cnt,ans;
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++){
            a[i]%=k;
            if(a[i])//判断0
                a[i]=k-a[i];//这就是需要增加的值
        }
        sort(a+1,a+n+1);//保证有序
        for(int i=2;i<=n;i++){
            if(a[i]&&a[i]%k==a[i-1]%k)
                a[i]=a[i-1]+k;//处理相邻冲突，x每次都要加1，所以相邻两个数不可以相等，处理成前一位加k
        }
        sort(a+1,a+n+1);
        if(a[n])//判断0
            cout<<a[n]+1<<endl;//处理最开始x由0变1的操作
        else
            cout<<0<<endl;
    }
    return 0;
}