题解 P3951 【小凯的疑惑】

infinityedge · 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 一定是合法的，所以满足性质

那么如果 k-1 合法，那么 k - 1 可以表示成

或

其中 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 的系数大于 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;
}