问题描述
小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入格式
两个正整数，表示每种包装中糖的颗数(都不多于1000)
输出格式
一个正整数，表示最大不能买到的糖数
样例输入1
4 7
样例输出1
17
样例输入2
3 5
样例输出2
7
#include#include #define MAX 10000000using 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#include #define MAX 10000000using 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次未出现不能买到的数，就说明之后的数都可以买到了。可惜我不能证明！！！