蓝桥杯 PREV-8 买不到的数目

数论 动态规划

题目描述

问题描述
小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。

本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

输入格式
两个正整数，表示每种包装中糖的颗数(都不多于1000)

输出格式
一个正整数，表示最大不能买到的糖数

样例输入1
4 7
样例输出1
17
样例输入2
3 5
样例输出2
7

关键点

• 倘若连续出现min(a, b)个 能被a 和 b组合出来的数, 那么后面的所有数都能通过添加min(a,b)来组合
  • eg. 对于a=4, b=7; 14 15 16 17 之后 18=14+4, 19=15+4 ... 后面的数全能被a,b表示出来
• 既然能组成所有的数，那么a和b一定是互质的。如果ab不是互质的他们组成的数总是最大公约数的倍数，那就不能组成后面所有的数。
• ab互质：不能组成的最大整数位：a*b-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 count = 0, ans = 0;
        int[] num = {a, b};
        int[] judge = new int[100000];
        judge[a] = 1;
        judge[b] = 1;

        for(int i=0;;i++){
            for(int j=0;j<2;j++) {
                if (i > num[j])
                    judge[i] += judge[i - num[j]];
            }
            if(judge[i] == 0) {ans = i; count = 0;}
            else count++;
            if(count >= Math.min(a, b)) break;
        }
        System.out.println(ans);
    }

}