小凯的疑惑

题目描述

小凯手中有两种面值互素的金币，面值为正整数 $a, b$ （ $1 \le a, b \le 10^9$ ），每种都有无数个。在不找零的情况下，有些价值他无法准确支付，输入数据保证这样的价值存在。输入格式：一行两个正整数 $a, b$ ，用一个空格隔开；输出格式：一个正整数 $N$ ，表示不能准确支付的最贵物品的价值。样例：输入 3 7，输出 11（凑不出的是 $1, 2, 4, 5, 8, 11$ ，最大为 $11$ ）。

思路

经典 Frobenius 数（Chicken McNugget 定理）：互素两币值凑不出的最大价值为 $ab - a - b$ 。按模 $a$ 分余数类，每类的可凑出数由其最小可达值 $y_r b$ （ $y_r$ 为使 $y_r b \equiv r \pmod a$ 的最小非负 $y$ ）加任意多个 $a$ 构成， $y_r$ 最大取 $a-1$ ，故该类凑不出的最大数为 $(a-1)b - a$ ，即答案。正确性两半成立： $ab-a-b$ 本身凑不出（模 $a$ 导出 $y \equiv -1$ 与 $0 \le y \le a-1$ 矛盾），更大的数按余数取合适的 $y$ 即可凑出。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 12:46
# update_at: 2026-10-02 12:46

import sys


def solve() -> None:
    a, b = map(int, sys.stdin.buffer.read().split())
    # 互素两币值不能凑出的最大值 = a*b - a - b（数论结论，证明见题解）
    print(a * b - a - b)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 16:00
 * update_at: 2026-10-06 16:00
 */
#include <cstdio>

typedef long long ll;

int main() {
    ll a, b; // 两种金币的面值，互素，最大 1e9，乘积约 1e18 需要 ll
    scanf("%lld %lld", &a, &b);
    // Frobenius 数：互素两币值凑不出的最大价值是 a*b - a - b
    printf("%lld\n", a * b - a - b);
    return 0;
}

目录

题目描述

思路

参考代码