2013省赛买不到的数目 java

分析 1.数论如果输入的两个数不互质，比如一个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)); }} 2.dp

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

【2013省赛买不到的数目 java】

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;}}	}}

2013省赛 买不到的数目 java

2013省赛买不到的数目 java