题解 | #[NOIP2017]小凯的疑惑#

exgcd的做法，题解区有一个这么讲的了，这里按照我自己的理解解释一遍。

首先是要求我们找到的最大的，那么必然存在有解。

因为和互质，那么一定存在解。将2式左右同时减1得到：。然后代入1的值得到： 。

3式无解，必然需要满足。又由于,同时都是正整数，那么ab一定异号。可以分成如下两种情况讨论，并且都需要满足：

• 当,那么必然大于等于0， 为了无解，需要让 ,也就是 ,贪心的取最大就是
• 当,那么必然大于等于0， 为了无解，需要让 ,也就是 ,贪心的取最大就是

需要注意，两种情况的x'和y'不一样。都是满足等式的情况下的最小值，这里也很好理解，因为x'和y'是此消彼长的存在，一个大，一个就会小，可以举个的例子。这样当越来越小，就越来越大为了。为了满足x 小于所有的，自然是取他的最小值，同理。

//exgcd
tuple<int,int,int> exgcd(int a,int b){
    if(b == 0) return {1,0,a};
    auto [nx,ny,g] = exgcd(b,a%b);
    return {ny,nx - a/b*ny,g};
}
void solve(){
    int a,b; cin >> a >> b;
    auto [x,y,g] = exgcd(a,b);
    //求出x的最小值
    int t = b/g;
    x = (x%t + t)%t;
    t = a / g;
    y = (y%t + t)%t;
    cout << (x - 1) * a + (y - 1) * b - 1 << endl;
}
//省略main