NOIP2017 小凯的疑惑 解题报告(赛瓦维斯特定理)

一、赛瓦维斯特定理

　　如果我直接说赛瓦维斯特定理，你可能并不知道它是什么（不然你也不会点进来看了）；那么如果我说\(NOIP\) \(2017\) \(D1\) $T$1小凯的疑惑，那你可能会恍然大悟。

其实，赛瓦维斯特定理就是：

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

那么，也就是小凯的疑惑中的\(a*b?a?b\)。

二、定理证明

不妨设 \(a < b\)
假设答案为 \(x\)
若
\(x \equiv ma \pmod b (1 \leq m \leq b - 1)\)

即
\(x = ma + nb (1 \leq m \leq b - 1)\)

显然当 \(n \geq 0\) 时 \(x\) 可以用 \(a\), \(b\) 表示出来，不合题意。

因此当 \(n = -1\) 时 \(x\) 取得最大值，此时 \(x = ma - b\)。

显然当 \(m\) 取得最大值 \(b - 1\) 时 \(x\) 最大，此时 \(x = (b - 1)a - b = ab - a - b\)
因此 \(a, b\) 所表示不出的最大的数是 \(ab - a - b\)

三、代码实现

#include
using namespace std;
int main(){
	long long a,b;
	cin>>a>>b;
	cout<