自创方法
前几项正常来求能否被凑出来, 直到能达到Math.max(n, m) + 2, 为什么加2, 防止越界
后面的话就是一个dp, 如何判断这个数是否能被凑出来, 那么看该数-n, -m时候能否被凑出
只要一个可以就是true, 否则是false, 至于这个范围为啥是n * m, 我也不清楚hh
这样的话, 就是近乎0(n * m)的时间复杂度
import java.util.*;
public class Main {
static int N = 1000010, n, m;
static boolean[] p = new boolean[N];
public static boolean get(int x) {
for (int i = 0; i < m; i ++ ) {
for (int j = 0; j < n; j ++ ) {
if (i * n + j * m == x) return true;
}
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
// 判断前几项
for (int i = 2; i <= Math.max(n, m) + 2; i ++ ) {
p[i] = get(i);
}
// 后面的用前面来推导
for (int i = Math.max(n, m) + 3; i <= n * m; i ++ ) {
if (p[i - n] || p[i - m]) p[i] = true;
else p[i] = false;
}
int res = 0;
for (int i = 1; i <= n * m; i ++ ) {
if (!p[i]) res = Math.max(res, i);
}
System.out.print(res);
}
}
官方做法
import java.util.*;
public class Main {
static int n, m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
System.out.print((n - 1) * (m - 1) - 1);
}
}