小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。
糖果不能拆包卖。 小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大
于17的任何数字都可以用4和7组合出来。 本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
分析：这道题可以直接暴力，枚举
1 #include<iostream> 2 #include<set> 3 using namespace std; 4 set<int> ss; 5 6 int main(int argc, char const *argv[]) 7 { 8 int a,b; 9 cin>>a>>b; 10 for( int i=0; i*a<=a*b; i++ ){/*枚举，上届不会比a*b大*/ 11 for( int j=0; j*b+i*a<=a*b; j++ ){ 12 ss.insert(i*a+j*b); 13 } 14 } 15 for(int i=a*b; i>=0; i-- ){ 16 if(ss.find(i)==ss.end()){ 17 cout<<i<<endl; 18 break; 19 } 20 } 21 return 0; 22 }
另一种做法就是利用数学结论：
a,b互质，则ax+by不能取到的最大的就是ab-a-b...
先证明一下，，，
a或者b是1的情况下容易证明.
以下情况都是a>1且b>1的情况.
首先证明ab-a-b不能表示成ax+by
假设ab-a-b=ax+by,那么ab=am+bn (m,n都大于等于1)
左边是a的倍数,右边am是a的倍数,那么要求bn也要是a的倍数
b不是a的倍数,只能要求n是a的倍数,这样的话,bn=bn'a>=ba
那么am=ab-bn所以am1矛盾.
接着证明ab-a-b+i能表示成ax+by(i>0)
因为ab互质,最大公约数就是1,根据辗转相减的方法知ma+nb=1,
不妨假设m>0,n1(m=0意味着nb=1不可能的),所以ab-a-b+i(ma+nb)=(im-1)a+(a+in-1)b
im-1>0,现在只要证明a+in-1>=0,因为ima+inb=i
如果,|in|>ja其中j>0,那么ima=i+|in|b>jab,所以im>jb
所以ima+inb=(im-jb)a-(|in|-ja)b=i,说明|in|>ja时,我们就能调整im,in使得|in|
很显然，题目中没有说明两个数字是互质，如果是2和4 ，通过程序得出的结果是2。
这个结果显然是错误的。但是很明显oj并没有设置这样的数。。。
1 #include<iostream> 2 using namespace std; 3 4 int main(int argc, char const *argv[]) 5 { 6 int a,b; 7 cin>>a>>b; 8 cout<<a*b-a-b<<endl; 9 return 0; 10 }
这里又有一条定理：当gcd(a,b) == 1 时（a和b互质），当c>a*b-a-b时，方程ax+by = c有非负解。
所以最大不能组合出的数目就是 a*b-a-b 。这里假设大家都知道这条定理，当然不知道也没关系，至少现在你知道了。。。