【题目描述】
暴力枚举 迭代写法
【思路】
分别枚举m、n的个数
for(m个数)
for(n个数)
k = m * m个数 + n * n个数
O(N^2),只能枚举答案在1000以内的
import java.util.Scanner;
public class Main{
static int N = 10010;
static int []f = new int [N];
public static void main(String args[]){
Scanner reader = new Scanner(System.in);
int n = reader.nextInt(), m = reader.nextInt();
for(int i = 0; i < N / m + 1; i ++)//枚举m的个数
for(int j = 0; j < N / n + 1; j++)//枚举n的个数
{
int k = m * i + n * j;
if( k >= N ) continue;
f[k] = 1;
}
for(int i = N - 1; i >= 0;i --)
if(f[i] == 0){
System.out.println(i);
break;
}
}
}
暴力枚举——递归写法
过5/10数据
import java.util.Scanner;
public class Main{
//判断x能否由m、n组成
public static boolean dfs(int x, int m, int n){
if( x < 0) return false;
//x == 0 说明x能由若干m、n组成
if( x == 0 ) return true;
if( x >= m && dfs(x - m, m, n)) return true;
if( x >= n && dfs(x - n, m, n)) return true;
return false;
}
public static void main(String args[]){
Scanner reader = new Scanner(System.in);
int m = reader.nextInt(), n = reader.nextInt();
for(int i = 1000; i >= 1; i --)
{
if(!dfs(i, m, n)){
System.out.println(i);
break;
}
}
}
}
错误写法:
对于有返回值的递归函数,要注意对中间结果的保存和处理,只是把它扔掉了
import java.util.Scanner;
public class Main{
//判断x能否由m、n组成
public static boolean dfs(int x, int m, int n){
if( x < 0) return false;
//x == 0 说明x能由若干m、n组成
if( x == 0 ) return true;
if( x >= m ) return dfs(x - m, m, n);
if( x >= n ) return dfs(x - n, m, n);
return false;
}
public static void main(String args[]){
Scanner reader = new Scanner(System.in);
int m = reader.nextInt(), n = reader.nextInt();
for(int i = 1000; i >= 1; i --)
{
if(!dfs(i, m, n)){
System.out.println(i);
break;
}
}
}
}
AC代码
引理
给定a,b,如果d =gcd(a, b) >1,那么其凡不是d倍数的a,b都凑不出,因此其不存在最大的凑不出的数。
结论
若a、b均为正整数且gcd(a,b) = 1, 那么 ax + by ,x >= 0, y >= 0,最大不能表示的数为 a*b - a - b
import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner reader = new Scanner(System.in);
int a = reader.nextInt(), b = reader.nextInt();
//公式: (a - 1) * (b - 1) - 1 =ab -a - b
System.out.println(a * b - a - b);
}
}