算法1
(暴力枚举)
枚举模式:枚举从1到1000所有数,判断其是否能被凑出来,从而得出不能被凑出的最大数
递归函数:bool dfs(int i,int m,int n)
递归函数参数含义:i为需要被判定的数,判断其是否能被凑出来
C++ 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
bool dfs(int i, int m, int n) {
if (i==0) return true;//若为0,代表可以凑出来
if (i >= m && dfs(i - m, m, n)) return true;//枚举用m凑数的情况
if (i >= n && dfs(i - n, m, n)) return true;//枚举用n凑数的情况
return false;
}
int main() {
int m, n;
cin >> m >> n;
int res = 0;
for (int i = 1; i <= 1000; i++) {
if (!dfs(i, m, n))//若不能凑出来,记录该数
res = i;
}
cout << res << endl;
}
时间复杂度:$O(n)$
注意:用该算法做会因为给的数字太大而超时,所以需要通过打表一些结果来找出规律,得出数学公式,大大降低算法时间复杂度
打表得出的结果
m=3
m n res
3 2 1
3 4 5
3 5 7
3 7 11
3 8 13
m=4
m n res
4 3 5
4 5 11
4 7 17
4 9 23
4 11 29
得出m和n最大能拼出来的数是n*(m-1)-m
算法2
(结论公式法)
C++ 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int m, n;
cin >> m >> n;
cout << (n*(m - 1) - m) << endl;//通过总结出来的公式直接得出m和n最大能凑出来的数
}
时间复杂度:$O(1)$
结论
如果a,b均是正整数且互质,那么由 ax+by(x≥0,y≥0)不能凑出的最大数是 ab−a−b(不互质的两个数凑不出最大数,及gcd(a,b)>1)