数学知识:
引理:给定a,b,若d=gcd(a,b)>1 , 则一定不能凑出最大数
如果 a,b 均是正整数且互质,那么由 ax+by, x≥0, y≥0 不能凑出的最大数是 (a−1)(b−1)−1 = ab - a -b
#include<iostream>
using namespace std;
int gcd(int a, int b){
return b ? gcd(b, a % b): a;
}
int main(){
int m, n;
cin >> m >> n;
if(gcd(m , n) > 1){
}
else{
cout << m * n - m - n << endl;
}
return 0;
}
也可以使用DP的方法,如果dp[i - m] 或 dp[i - n] 成立(可以被凑出来),则dp[i]也可以被凑出
而且最大数从m * n开始枚举,因为m * n是一个周期