算法1

(暴力枚举) $O(n^2)$

若存在无法组合的数k，对于k~k+m+n都组合，则k为最大无法组合数，找到这个k即可

时间复杂度

O(n^2)，部分案例超时

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <sstream>
#include <algorithm>
using namespace std;

bool judge(int x, int m, int n);
int main(int argc, char** argv) {
    int m,n;
    cin >> m >> n;
    int maxContinue = 0;
    int k = 3;
    while(1) {
        if(maxContinue == m + n)// m + n 为一个周期，为什么选择 m + n？
            break;
        if(judge(k,m,n))
            maxContinue++;
        else
            maxContinue = 0;
        k++;
    }
    cout << k - m - n - 1;
    return 0;
}

bool judge(int x, int m, int n) 
{
    int maxDivisor = x/m > x/n ? x/m : x/n;
    for(int i = 0; i < maxDivisor; i++) {
        if(x-i*m >= 0 && (x-i*m) % n == 0)
            return true;
        if(x-i*n >= 0 && (x-i*n) % m == 0)
            return true;
    }
    return false;
}

算法2

空间换时间 $O(n)$

MAXINT 为0x3fffffff时RE，在DevCpp可以运行，什么原因？
MAXINT 为0xfffffff时AC

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <sstream>
#include <algorithm>
using namespace std;

#define MAXINT 0xfffffff
bool dp[MAXINT];

int main(int argc, char** argv) {
    int m,n;
    cin >> m >> n;
    int maxContinue = min(m,n);
    int k = min(m,n);
    int mmin = min(m,n);
    int mmax = max(m,n);
    dp[0] = true;
    while(1) {
        if(maxContinue == m + n)// m + n 为一个周期，为什么选择 m + n？
            break;
        if(k >= mmax)
            dp[k] = dp[k- mmax] | dp[k- mmin];
        else
            dp[k] = dp[k- mmin];
        if(dp[k])
            maxContinue++;
        else
            maxContinue = 0;
        k++;
    }
    cout << k - m - n - 1;
    return 0;
}