自动搬运

查看原文

来自洛谷，原作者为

	xuyixuan_123 叫我Air/空气

搬运于2025-08-24 21:18:21，当前版本为作者最后更新于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;
}