CF1883C Raspberries

One_JuRuo · 2023-10-23 13:22:59 · 题解

思路

最开始晃眼一看，感觉很难，仔细一读题，哦，原来 k\in [2,5] 啊。

首先如果 k 是质数，也就是 k 不等于 4 的情况，必须要有一个数是 k 的倍数，那么计算每个数需要的操作数，取最小即可。

如果 k 不是质数，也就是 k 等于 4 的情况，要么是一个数是 4 的倍数，要么有两个数是 2 的倍数，那么取最小即可。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,m,a,ans;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m),ans=m+2;
        if(m==4)//当时想复杂了，所以写得又臭又长
        {
            ans=2;
            if(n==1)
            {
                scanf("%d",&a);
                printf("%d\n",(a%4==0)?0:(m-a%m));
            }
            else
            {
                int num=4;
                for(int i=1;i<=n;++i)
                {
                    scanf("%d",&a),ans-=(a%4==0)?2:(a%2==0)?1:0;
                    if(a%4==3) num=1;
                    if(a%4==2) num=min(num,2);
                }
                printf("%d\n",min(num,max(ans,0)));
            }
            continue;
        }
        for(int i=1;i<=n;++i) scanf("%d",&a),ans=min(ans,(a%m==0)?0:(m-a%m));
        printf("%d\n",ans);
    }
    return 0;
}