蓝桥杯C/C++省赛：买不到的数目

叶茂林

发布于 2023-07-30 11:59:55

2240

发布于 2023-07-30 11:59:55

题目描述

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

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

要求输出：一个正整数，表示最大不能买到的糖数

不需要考虑无解的情况

例如：用户输入： 4 7 程序应该输出： 17

再例如：用户输入： 3 5 程序应该输出： 7

思路分析

方法一：

图论知识：

自然数a,b互质,则不能表示成ax+by（x,y为非负整数）的最大整数是ab-a-b。

极其NB的性质，高级的数学定理搞定一切美妙的算法。

方法二：

数学知识：

a和b线性组合不能表示的数字介于a+b-1和a和b的最小公倍数之间。

这里需要暴力遍历，其实这个性质就解决了遍历的上限。

我们需要三个函数，一个求最大公因数，一个求最小公倍数，一个检查是否不能由a和b表示。

我的疑惑

有没有懂哥解释一下为什么这两个性质是成立的？

AC代码（方法一）

#include <bits/stdc++.h>

using namespace std;

int main() {
    int m,n;
    cin>>m>>n;
    cout<<m*n-m-n;
    return 0;
}

AC代码（方法二）

#include <bits/stdc++.h>

using namespace std;

int GCD(int a, int b) {
    while (a % b) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return b;
}

int LCM(int &a, int &b) {
    return a * b / GCD(a, b);
}

bool Check(int &test, int &a, int &b) {
    for (int i = 0; i <= b; i++)
        for (int j = 0; j <= a; j++)
            if (test == i * a + j * b)
                return false;
    return true;
}

int main() {
    int m, n, i;
    cin >> m >> n;
    for (i = LCM(m, n) - 1; i >= m + n - 1; i--)
        if (Check(i, m, n)) {
            cout << i;
            return 0;
        }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-10-29，如有侵权请联系 cloudcommunity@tencent.com 删除

c++