小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
两个正整数，表示每种包装中糖的颗数(都不多于1000)
一个正整数，表示最大不能买到的糖数
#include<iostream> #include<cstring> #define MAX 10000000 using namespace std; bool a[MAX]; int x, y, res; void _solv() { cin >> x >> y; memset(a, 0, sizeof(a)); a[0] = 1; for (int i = 1; i < MAX; i++){ if (i >= x&&a[i - x])a[i] = 1; else if (i >= y&&a[i - y])a[i] = 1; } res = 0; for (int i = 1; i < MAX; i++){ if (i>res&&!a[i])res = i; } } int main() { _solv(); cout << res << endl; system("pause"); return 0; }
本质：从0开始，看x和y能否覆盖到这个数。
按照蓝桥杯上给的提示，说欧几里得也能做，所以又试了一下，果然AC了！
//用数论或欧几里得算法 #include<iostream> #include<cstring> #define MAX 10000000 using namespace std; bool a[MAX]; int x, y, res; void _solv() { cin >> x >> y; memset(a, 0, sizeof(a)); a[0] = 1; for (int i = 1; i < MAX; i++){ if (i >= x&&a[i - x])a[i] = 1; else if (i >= y&&a[i - y])a[i] = 1; } res = 0; for (int i = 1; i < MAX; i++){ if (i>res&&!a[i])res = i; } } int _test() { int i = 1; while (i){ if (i == 5)return 5; i++; } } bool _Euclid(int a) { if (a <= 0)return false; if (a%y == x||a%y==0){ return true; } else { return _Euclid(a - x); } } void _solv2() { cin >> x >> y; res = 0; int time = 0; for (int i = 1; i < MAX; i++){ if (time == 10000)break; if (i>res && i%x!=0 && i%y!=0 && !_Euclid(i-x)){ res = i; time = 0; } else{ time++; } } } int main() { _solv(); cout << res << endl; //cout<<_test(); _solv2(); cout << res << endl; system("pause"); return 0; }
只要注意一下连续time次未出现不能买到的数，就说明之后的数都可以买到了。可惜我不能证明！！！
原文：http://www.cnblogs.com/littlehoom/p/3548642.html