题解 P3951 【小凯的疑惑】

#### 说明 这个做法是我在考场上想出来的 ex\_gcd 做法，当时并没有想到打表，所以向发表一下让大家彻底摆脱小学奥数带来的阴影，我现在仍然认为，ex\_gcd 是这道题的标算。 #### 题解 首先，我们发现这两个数是**互质**的，并且有**无限**个。很容易想到不定方程 $ax + by = gcd(a, b)$ ，其中 $gcd(a, b) = 1$ 。 然后我们考虑，对于所有可行的能被 $a$ 和 $b$ 表示出来的数 $k$ ，都存在 $x \geq 0, y \geq 0,ax + by = k$。 现在我们要构造的是**最大的不合法的数**，显然，这个数 $+ 1$ 一定是一个合法的数，转化成了求**最大的减一后不合法的数**。 由于这个数 $k$ 一定是合法的，所以满足性质 $$\exists x \geq 0, \exists y \geq 0,ax + by = k$$ 那么如果 $k-1$ 合法，那么 $k - 1$ 可以表示成 $$a \left ( x - x' \right ) + b \left ( y - y' \right ) = k$$ 或 $$a \left ( x - x'' \right ) + b \left ( y - y'' \right ) = k$$ 其中 $x',y'$ 表示 $ax + by = 1$ 的 $x$ 最小且非负的整数解; $x'',y''$ 表示 $ax + by = 1$ 的 $y$ 最小且非负的整数解。 那么现在只需要让 $x - x'< 0$ 并且 $y - y'' < 0$ 即可 那么最后的**最大的减一后不合法的数**就是 $$a \left ( x' - 1 \right ) + b \left ( y'' - 1 \right ) $$ 那么最后的**答案**就是 $$a \left ( x' - 1 \right ) + b \left ( y'' - 1 \right ) - 1$$ #### 证明： 首先充分性成立。 然后证明必要性：若$a \left ( x' - 1 \right ) + b \left ( y'' - 1 \right ) $不是**最大的减一后不合法的数**，那么一定存在一个更大的数，显然该数的 $a$ 的系数大于 $x' - 1$ 或 $b$ 的系数大于 $y'' - 1$ （如果都小于等于，那么该数不会比当前数大）。显然，减一后仍然是合法的。所以必要性成立。 综上， $a \left ( x' - 1 \right ) + b \left ( y'' - 1 \right ) - 1$ 是最大的不合法的数。 #### 代码： ```cpp #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; ll gcd(ll a, ll b){ return b == 0 ? a : gcd(b, a % b); } void ex_gcd(ll a, ll b, ll &x, ll &y){ if(b == 0){ x = 1, y = 0; return; } ex_gcd(b, a % b, y, x); y -= (a / b) * x; } ll a, b; int main(){ cin >> a >> b; if(a > b) swap(a, b); ll x, y; ex_gcd(a, b, x, y); if(x > 0){ swap(a, b); swap(x, y); } ll tmp = (-x) / b; x = x + tmp * b; y = y - tmp * a; while(x < 0) x = x + b, y = y - a; while(x > 0) x = x - b, y = y + a; ll ans; ll xx2 = x + b; ans = a * (xx2 - 1) + b * (y - 1); cout << ans - 1 << endl; return 0; } ```