CF1883C题解

allen2010 · 2023-11-06 17:41:42 · 题解

思路

考虑到 k 较小，可以先从 k 入手。

可以发现，当 k 为质数，即 k = 2,3,5 时，只要把 a 中的一个数改成其倍数即可。

当 k = 4 时，分两种情况讨论：

1. 将 a 中两个数分别修改成 2 的倍数。

2. 将 a 中一个数修改成 4 的倍数。

取两种情况最小值即可。

代码

#include <bits/stdc++.h>
using namespace std;
int a[100007];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        int minn=0xfffffff;
        for(int i=0;i<n;i++) cin>>a[i];
        if(k!=4){
            for(int i=0;i<n;i++)
            {
                int x=a[i];
                minn=min(minn,(x%k!=0?k-x%k:0));
            }
        }else{
            for(int i=0;i<n;i++)
            {
                int x=a[i];
                minn=min(minn,(x%k!=0?k-x%k:0));
            }
                int minn1=0xfffffff;
            k=2;
            int id=0;
            for(int i=0;i<n;i++)
            {
                int x=a[i];
                if(minn1>(x%k!=0?k-x%k:0))
                {
                    minn1=(x%k!=0?k-x%k:0);
                    id=i;
                }
            }
            a[id]=0xfffffff;
            int minn2=0xfffffff;
            for(int i=0;i<n;i++)
            {
                int x=a[i];
                minn2=min(minn2,(x%k!=0?k-x%k:0));
            }
            minn1+=minn2;
            minn=min(minn1,minn);
        }
        ansok:
            cout<<minn<<endl;
    }
    return 0;
}