CH Adera 三(ZZB的数学作业-构造法初讲)

CH Adera 3(ZZB的数学作业-构造法初讲)

描述把一个正整数M分成P个不超过K的正整数的和，满足分成的数不是N的倍数，并且P也不是N的倍数，求这样的P最小是多少？”

输入格式一个测试点不超过10组数据，每行三个整数N、M、K代表一组数据，以EOF结尾。

输出格式对于每组数据输出一行，一个整数，即最小的P。

样例输入

3 11 62 12 47

样例输出

4-1

数据范围与约定

对于20%的数据，1<=N，M，K<=20。
对于60%的数据，1<=N，K<=10000。
对于另20%的数据，1<=K<=2。
对于100%的数据，1<=N，M，K<=10^9。

特判 

n=1 m%n肯定不行

n=2 m是偶数 奇数个奇数和≠偶数 不行

否则找最小的k

现在开始维护p，各种特判

由于最后多出来的一部分=k-1是不能合并 所以必须拆

最后维护p

#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<functional>#include<iostream>using namespace std;#define MAXN (1000000000)int n,m,k;int main(){while (cin>>n>>m>>k){if (n==1||n==2&&!(m%2)){puts("-1");continue;}while (!(k%n)) k--;if (k==1){if (m%n) cout<<m<<endl;else puts("-1");continue;}int ans=(m-1)/k+1;if (ans==1&&!(m%n)) ans++;if (!((k-1)%n)&&m%k==k-1) ans++;if (!(ans%n)) ans++;cout<<ans<<endl;}return 0;}