侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-02-21 / 0 评论 / 0 点赞 / 88 阅读 / 869 字
温馨提示:
本文最后更新于 2023-02-21,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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


小明开了一家糖果店。

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

糖果不能拆包卖。

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

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

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

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

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

输入格式

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

输出格式

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

数据范围

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

输入样例:

4 7

输出样例:

17

解题

方法一:枚举

思路

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

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

代码

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,ba, b 使正整数且互质,那么由 ax+b,x0,y0ax + b, x \ge 0, y \ge 0 不能凑出的最大数是 ababab - 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);
    }
}
0

评论区