【数学, 枚举】买不到的数目

题目

1205. 买不到的数目 - AcWing题库

---

小明开了一家糖果店。

他别出心裁：把水果糖包成4颗一包和7颗一包的两种。

糖果不能拆包卖。

小朋友来买糖的时候，他就用这两种包装来组合。

当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。

你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。

大于17的任何数字都可以用4和7组合出来。

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

输入格式

两个正整数 $n,m$ ，表示每种包装中糖的颗数。

输出格式

一个正整数，表示最大不能买到的糖数。

数据范围

$2 \le n,m \le 1000$ ，
保证数据一定有解。

输入样例：

4 7

输出样例：

17

解题

方法一：枚举

思路

题目既然保证数据一定有解，那么解最大一定不会超过 $n \times m$ ，证明：
反证法，设 $n, m$ 最大不能组合出的数字为 $x$ 且 $x > n \times m$ ，那么 $nm + x, 2nm + x, 3nm+x, \dots$ 必然也不能被组合出来，这样以来就无解了，与题目给出的条件不符，所以最大不能组合出的数字一定不会超过 $n \times m$ 。

首先使 $n,m$ 中较小的为 $n$ ，较大的为 $m$ ，那么 $[1, n-1]$ 之间的数一定组合不出来，$0$ 一定可以组合出来。然后枚举 $i \in [n, n \times m - 1]$ ，如果 $i - n$ 可以被组合出来或者 $i - m (i \ge m)$ 可以被组合出来那么 $i$ 就一定能被组合出来，否则更新最大不能组合出的数字。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        if (n > m) {
            int tmp = m;
            m = n;
            n = tmp;
        }
        boolean[] f = new boolean[n * m];
        f[0] = true;
        int ans = n - 1;
        for (int i = n; i < n * m; ++i) {
            if (f[i - n] || i >= m && f[i - m]) f[i] = true;
            else ans = i;
        }
        System.out.println(ans);
    }
}

方法二：数学

思路

如果 $a, b$ 使正整数且互质，那么由 $ax + b, x \ge 0, y \ge 0$ 不能凑出的最大数是 $ab - a - b$ 。

证明见：数论：px+py 不能表示的最大数为pq-p-q的证明

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        if (n > m) {
            int tmp = m;
            m = n;
            n = tmp;
        }
        boolean[] f = new boolean[n * m];
        f[0] = true;
        int ans = n - 1;
        for (int i = n; i < n * m; ++i) {
            if (f[i - n] || i >= m && f[i - m]) f[i] = true;
            else ans = i;
        }
        System.out.println(ans);
    }
}