AcWing 1205. 买不到的数目
原题链接
简单
作者:
Bear_King
,
2021-01-11 21:24:51
,
所有人可见
,
阅读 337
暴力很快乐,但被卡时间就过不了
先用下面的爆搜,打表然后找规律,推数学公式
#include<iostream>
using namespace std;
bool dfs(int m,int p,int q)
{
if(!m) return true;//是0就结束
if(m >= p && dfs(m - p,p,q)) return true;//用p凑
if(m >= q && dfs(m - q,p,q)) return true;//用q凑
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;
}
学好数学,还是香的呀批
找完规律,推出公式:(p-1)*(q-1)-1
#include<iostream>
using namespace std;
int main()
{
int p,q;
cin>>p>>q;
cout<<(p-1)*(q-1)-1<<endl;
return 0;
}