2013省赛 买不到的数目 java

如果输入的两个数不互质，比如一个2、一个4，那么最大不能达到的数字为无穷，即无解，题目保证此题有解；那么输入的两个数就是互为质数；
对互质的两个数：

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		System.out.println(a * b - (a + b));
	}
}

递推关系就是，当前数 i 减去 a 或 b 可以被凑出来时 ，那么这个数就可以被凑出来;如果i这个数可以凑出来，用dp数组标记为1；结果不会超过a*b，直接在这里面通过递推去找能凑的值；

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int[] dp = new int[a * b + 5];// 用来表示某个数能否凑到
		dp[a] = 1;//初始化这个值可以凑到
		dp[b] = 1;
		for (int i = a; i <= a * b; i++) {
			if (dp[i - a] == 1)//表示当前值减去a可以凑到，那么加上a肯定能凑到
				dp[i] = 1;
		}
		for (int i = b; i <= a * b; i++) {
			if (dp[i - b] == 1)
				dp[i] = 1;
		}
		for (int i = a * b; i > 0; i--) {//倒着找
			if (dp[i] == 0) {//这个就是最大的没凑到的数
				System.out.println(i);
				break;
			}
		}
	}
}