AcWing 1205. 买不到的数目
原题链接
简单
#include <iostream>
using namespace std;
/*
如果p和q的最大公约数为d
那么无论怎么组合都一定是d的倍数
那不是d的倍数就一定无解
比如6和2,那么所有5的倍数都无解,5的n次方无穷大他也凑不出来
所以d > 1一定无解
*/
//打表找规律
/*
int p,q;
bool dfs(int m,int p,int q)
{
if(!m) 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()
{
cin>>p>>q;
int res = 0;
for(int i = 1;i <= 1000;i++)
{
if(!dfs(i,p,q)) res = i;
}
cout<<res;
return 0;
}
*/
/*
4 3 5
4 5 11
4 7 17
4 9 23
2 3 1
2 5 3
2 7 5
2 9 7
2 11 9
打表可知公式为(p-1)(q-1) - 1
*/
//裴蜀定理
/*
对任何整数a、b和它们的最大公约数d,关于未知数x和y的线性不定方程(称为裴蜀等式):若a,b是整数,且gcd(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。
它的一个重要推论是:a,b互质的充要条件是存在整数x,y使ax+by=1.
*/
int main()
{
int p,q;
cin>>p>>q;
cout<<(p-1)*(q-1)-1;
}