题解：P8348 「Wdoi-6」未知之花魅知之旅

如果有两项 a,b，不考虑大小限制，则下一项只能是：

由于 k 是正整数，所以下一项不能是负数，于是至多有两种情况：a+b 和 |a-b|。归纳得出数列中的每一项是若干个 a 和若干个 b 的和。

然后我们需要证明：如果从两项 (a,b) 可以操作得出 (c,d)，则 (c,d) 可以通过操作还原成 (a,b)。

还原方法：假设 (b,a) 做加法变成了 (a,a+b)，我们可以减法变成 (a+b,b) 再变成 (b,a)。

如果 (b,a) 做减法变成了 (a,a-b)，我们可以做减法变成 (a-b,b)，做加法变成 (b,a)，做加法变成 (a,a+b)，做减法变成 (a+b,b)，做加法变成 (b,a+2b)，做减法变成 (a+2b,a+b)，做减法变成 (a+b,a)，做减法变成 (a,b)。

如果 (b,a) 做减法变成了 (a,b-a)，我们可以做加法变成 (b-a,b)，做减法变成 (b,a)。

这就表示，每一步都是可逆的。我们只要重复这些步骤，一定能够还原。

那么，我们要如何从 (a,b) 出发，使得相邻两项为 (x,y)？

注意到如果 (a,b) 和 (x,y) 都能通过操作达到一个 (c,d)，那么 (a,b) 一定能先操作变为 (c,d) 再到 (x,y)。

然后，根据 Bezout 定理（大概是叫这个名字），存在一对最小的正整数 (c,d)。我们只需要判断 (a,b) 和 (x,y) 操作得到的 (c,d) 是否相同。

于是模拟即可。我采用的是类似 Euclid 算法的方式。

注意如果 a_0,a_1,x,y 中有至少一个小于 k 就无解。

#include<bits/stdc++.h>
using namespace std;
int t;
int a0, a1, x, y, k;
void work(int &a, int &b){//求最小数对
    while (1){
        if (a < b){
            if ((b - k) < a)
                break;
            bool fl = ((b - k) / a) & 1;
            b -= (b - k) / a * a;
            if (fl)
                swap(a, b);
        }else if (a != b){
            if ((a - k) < b)
                break;
            bool fl = ((a - k) / b) & 1;
            a -= (a - k) / b * b;
            if (fl) 
                swap(a, b);
        }else
            break;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> t;
    while (t--){
        cin >> a0 >> a1 >> x >> y >> k;
        if (k > min(min(a0, a1), min(x, y))){//不能小于 k
            cout << "no\n";
            continue;
        }
        int ta0 = a0, ta1 = a1, tx = x, ty = y;
        work(ta0, ta1);
        work(tx, ty);
        if (ta0 != tx || ta1 != ty)//判断最小数对是否相等
            cout << "no\n";
        else
            cout << "yes\n";
    }
    return 0;
}