复赛一：小凯的疑惑(math)

洛谷：P3951
OJ: I3951

费罗贝努斯问题（Frobenius Coin Problem）是数论中的一个经典问题，主要研究如何用给定的一组互质的正整数（通常称为“硬币面值”）来表示其他整数。具体来说，问题通常包括以下几个方面：

问题描述

给定一组互质的正整数 a₁,a₂,…,a_n，这些整数代表不同面值的硬币，且每种面值的硬币数量无限。费罗贝努斯问题主要研究以下两个问题：

1. 可表示性问题：给定一个正整数 N，是否存在非负整数 x₁,x₂,…,x_n​ 使得 N=a₁x₁+a₂x₂+…+a_nx_n
2. 最大不可表示数：在所有无法表示的正整数中，最大的那个数称为最大不可表示数（Frobenius Number）。

二元费罗贝努斯问题

对于只有两个互质正整数 a 和 b的情况，费罗贝努斯问题有一个简单的闭式解：g(a,b)=ab−a−b

这个结果意味着，对于两个互质的正整数 a 和 b，最大的无法表示的正整数是 ab−a−b。例如，对于 a=3 和 b=7，最大不可表示数为 3×7−3−7=11，这与之前的编程题目示例相符。

证明思路

简要证明如下：

1. 线性组合表示：由于 a和 b 互质，根据贝祖定理（Bézout’s identity），存在整数 x 和 y 使得 ax+by=1。因此，对于任意整数 N，存在整数解 xx和 y 使得 ax+by=N。
2. 非负整数解：但题目要求 x 和 y都是非负整数。通过数论中的进一步分析，可以证明当 N≥ab−a−b+1 时，总存在非负整数解使得 N=ax+by。而 ab−a−b则是最大的无法表示的数。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/**************************************************************** 
 * Description: 2017年提高组第一题  小凯的疑惑
 * Author: Alex Li
 * Date: 2024-09-20 18:19:46
 * LastEditTime: 2024-10-01 14:14:08
****************************************************************/
#include <iostream>

using namespace std;

int main() {
    // freopen("math.in","r",stdin);
    // freopen("math.out","w",stdout);
    int a, b;
    // 读入两个正整数 a 和 b
    cin >> a >> b;
    
    // 根据公式计算最大无法支付的金额 N = a * b - a - b
    int N = a * b - a - b;
    
    // 输出结果
    cout << N << endl;

    return 0;
}