题解 P3951 【小凯的疑惑】

2017-11-19 21:37:12


说明

这个做法是我在考场上想出来的 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$ 是最大的不合法的数。

代码:

#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;
}