AcWing 1205. 买不到的数目

如果不知道公式的话，可以用打表的方法来找一下规律。

打表代码：

#include<iostream>
using namespace std;
bool dfs(int i,int n,int m)
{
    if(i==0)return true;
    if(i>=n&&dfs(i-n,n,m))return true;
    if(i>=m&&dfs(i-m,n,m))return true;
    return false ;
}
int main()
{
    int n,m,i,res;
    cin>>n>>m;
    for( i=1;i<=1000;i++)
    {
        if(!dfs(i,n,m))res=i;
    }
    cout<<res<<endl;
}

当然，仅仅靠暴搜是不能ac的，因为i的上限不好确定，容易超时。

因为如果 a,b 均是正整数且互质，那么由 ax+by,x≥0,y≥0 不能凑出的最大数是 (a−1)(b−1)−1。

所以只要输出a*b-a-b即可。