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即可。
比亚迪成长空间 169人发布
投递海康威视等公司10个岗位 >