点击打开链接
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 54 Solved: 43 [Submit][Status][Web Board]
小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。 小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。 你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。 本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
两个正整数，表示每种包装中糖的颗数(都不多于1000)
一个正整数，表示最大不能买到的糖数
4 7
17
历届试题
解题思路：
首先要明确，不可能的数目肯定比两数的最小公倍数要小，假设是4与7，至于为什么我也不是很清楚，就是一种猜测然后这样做下去就对了……之后就是用常规方法，建立3个for循环，第一个是去循环1-gbs(4,7)之间的数，第二个和第三个循环也是按照常规去4的个数和7的个数，当他们的乘积之和等于第一个循环中的i，则说明是可能数，反之亦然。
这里有个小细节，就是他们的上界该如何处理，这里我觉得是将gbs(4,7)/4+1，也就是说将最小公倍数除以较小的数+1，这样既不会使上界太大时间超限，也不会出现4或7的个数不够的问题。
代码：
#include<stdio.h> int gcd(int a,int b){ int x=a; while(x!=0){ x=a%b; a=b; b=x; } return a; } int gbs(int a,int b){ int x; x=a*b/gcd(a,b); return x; } int main() { int a,b,n,i,gcd,ans=0,flag=0,t,x,k,j; scanf("%d%d",&a,&b); gcd=gbs(a,b); if(a<b){ t=a; a=b; b=t; } x=(gcd/b)+1; for(i=gcd;i>=1;i--){ flag=0; for(k=0;k<=x;k++){ for(j=x;j>=0;j--){ if(!(k==0 && j==0)){//避免除数为0 if(i%(a*k+b*j)==0){ flag=1; } } } } if(flag==0){ ans=i; break; } } printf("%d\n",ans); return 0; }
