CH Adera 3(ZZB的数学作业-构造法初讲)
描述
把一个正整数M分成P个不超过K的正整数的和,满足分成的数不是N的倍数,并且P也不是N的倍数,求这样的P最小是多少?”
输入格式
一个测试点不超过10组数据,每行三个整数N、M、K代表一组数据,以EOF结尾。
输出格式
对于每组数据输出一行,一个整数,即最小的P。
样例输入
3 11 6 2 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; }
发表评论