AcWing 1205. 买不到的数目
原题链接
简单
//打表 找规律
//引理:给定a,b,若d=gcd(a,b)>1 则一定不能凑出最大数
//结论:如果 a, b 均是正整数且互质,那么由 ax+by, x≥0 ,y≥0, ax+by, x≥0, y≥0 不能凑出的最大数是 (a−1)(b−1)−1
#include <iostream>
using namespace std;
//给定一个m,是否能用p和q凑出来
bool dfs(int m,int p,int q)
{
if(m == 0) return true;
if(m >= p && dfs(m - p,p,q)) return true;
if(m >= q && dfs(m - q,p,q)) return true;
return false;
}
int main()
{
int p,q;
cin >> p >> q;
int res = 0;
for(int i = 1; i <= 1000;i ++)
{
if(!dfs(i,p,q)) res = i;
}
cout << res << endl;
return 0;
}