题解：B4284 [蓝桥杯青少年组省赛 2022] 组合

Night_Echo · 2025-05-11 17:09:06 · 题解

思路：

塞瓦维斯特定理

已知 a 和 b 为大于1的正整数，且 \gcd(a,b)=1 ，则使不定方程 ax + by=C 不存在非负整数解的最大整数为 C=a \times b − a − b。

于是就有了这个公式：

当然，我们有了公式还不行，还得有证明。

证明:

• 我们先来证明 a \times b - a - b 一定不能被取到。利用反证法，我们假设存在 x,y \ge 0 满足 ax + by=a \times b - a - b 。我们将 ab 除到左边来，即 a(x + 1) \div ab + b(y + 1) \div ab=1 ，在消一下即可得到 (x + 1) \div b+(y + 1) \div a=1 。这与我们假设中的 a(x + 1)+b(y + 1)=ab ， a \ge 0,b \ge 0 矛盾。因此，假设不成立，即不存在 x,y \ge 0 ，满足 ax + by=a \times b - a - b 。
• 接下来，我们需要证明当 C>a \times b - a - b 时， ax + by=C 一定存在非负整数解。考虑到 ax + by = C 可以通过扩展欧几里得算法求解，而扩展欧几里得算法可以在 \gcd(a,b)=1 的情况下找到 ax + by = \gcd(a,b) 的整数解。由于 a 和 b 互质，我们可以找到 ax+by=1 的整数解。因此，对于任何大于 a \times b - a - b 的 C ，我们都可以通过将 ax + by = 1 的解乘以适当的系数来找到 ax + by = C 的非负整数解。

综上所述，我们已经证明了塞瓦维斯特定理（不定方程）：对于互质的正整数 a 和 b ，不定方程 ax+by=C 不存在非负整数解的最大整数 C 等于 a \times b - a - b。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
cin>>n>>m;
cout<<n*m-n-m;
return 0;
}