跳至正文

1 条题解

  • 0
    @ 2026-10-8 18:53:36

    【本题解由站长编写】

    两个包装规格 a、b 由输入给出(不是硬编码的 4 和 7),求最大的、无法用若干个 a 包和若干个 b 包凑出的整数。当 gcd(a,b)=1 时经典结论是最大不能表示的数为 a*b - a - b(Frobenius 数);三组数据(10 13→107、30 41→1159、257 191→48639)都与该公式精确吻合。不放心时也可以用 DP 兜底:dp[0]=true,dp[i] = (i>=a && dp[i-a]) || (i>=b && dp[i-b]),在 0..a*b 范围内找最后一个 dp[i]==false 的 i。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        int a, b;
        cin >> a >> b;
        // 两个规格互质时,最大不能凑出的数就是 a*b-a-b
        cout << a * b - a - b << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    4096
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者