题目重述

我们需要将数字$M$表示为若干个不超过$K$的正整数的和，满足以下条件：

1. 每个加数不能被$N$整除
2. 加数的总数不能被$N$整除

目标是找到满足条件的最小加数数量，如果无法表示则返回$-1$。

解题思路

1. 关键观察：

   • 设最大可用加数为$K' = K$（若$K \mod N \neq 0$）或$K' = K-1$（若$K \mod N = 0$）
   • 最小加数数量$L$满足： [ L = \lceil \frac{M}{K'} \rceil ]
   • 需要保证$L \mod N \neq 0$

2. 特殊情况处理：

   • 当$N=1$时：所有数都能被$1$整除，直接返回$-1$
   • 当$K'<1$时：无可用的加数，返回$-1$

3. 调整策略：

   • 若初始$L \mod N = 0$，则尝试：
     • 增加$L$至$L+1$（需验证可行性）
     • 或减少最大加数至$K'-1$重新计算$L$

算法实现

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

int main()
{
	int tmp,k,m,n,ans,t,res,tmpres;
	scanf("%d",&t);
	while(t--)
	{
		ans=0;
		scanf("%d%d%d",&n,&m,&k);
		if(n==1)
		{
			printf("-1\n");
			continue;
		}
		if(k==1)
		{
			if(m%n==0)
				printf("-1\n");
			else printf("%d\n",m);
			continue;
		}
		if(n==2)
		{
			if(m%n==0) printf("-1\n");
			else
			{
				if(k%2==0) k--;
				ans=m/k;
				res=m%k;
				if(res>0)
				{
					ans++;
					if(res%2==0)ans++;
				}
				printf("%d\n",ans);
			}
			continue;
		}
		if(k%n==0) k--;
		res=m%k;
		ans+=m/k;
		if(res==0)
		{
			if(ans%n==0) ans++;
			printf("%d\n",ans);
			continue;
		}
		else//res>0
		{
			ans++;
			if(ans%n==0) ans++;
			else
			{
				if(res%n==0)
				{
					if(ans==1) ans++;
					else if((k-1)%n==0)
					{
						bool flag=false;
						for(int i=1;i<n&&i+res<=k&&i<k;i++)
						{
							if((res+i)%n!=0&&(k-i)%n!=0)
							{
								flag=true;
								break;
							}
						}
						if(!flag)
						{
							ans++;
							if(ans%n==0) ans++;
						}
					}
				}
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}