P8348 题解

Miyamizu_Mitsuha · 2023-07-30 11:02:53 · 题解

首先，如果 k 大于 x、y、a_0 或 a_1，那么肯定无法构造满足要求的数列，直接 no。因为每个数都不小于 k。

化简数对的话，直接减肯定不行，太慢了，直接 T 飞。遂辗转相除法化简 (a_0, a_1) 和 (x, y)，让他们在满足条件的情况下尽量小。

• 如果 a_0 > n \times a_1（其中 n 是一个偶数），则将 (a_0, a_1) 变为 (a_0 - n \times a_1, a_1)；
• 如果 a_1 > n \times a_0，则将 (a_0, a_1) 变为 (a_0, a_1 - n \times a_0)。

以上目的是化简到最小。数对就转变成了大于等于 k 的最小状态。

对 (x, y) 也执行同样的化简操作。

最后，判断化简后的数对 (a_0, a_1) 和 (x, y) 是否相等，输出 yes，否则输出 no。

#include <iostream>
using namespace std;

void sf(int &a, int &b, int k) {//化简
    while (true) {
        if (a < b) {
            int d = (b - k) / a;
            if (!d) break;
            b -= d * a;
            if (d & 1) swap(a, b);
        } else if (a > b) {
            int d = (a - k) / b;
            if (!d) break;
            a -= d * b;
            if (d & 1) swap(a, b);
        } else break;
    }
}

bool pd(int a, int b, int x, int y, int k) {
    if (k > x || k > y || k > a || k > b)//如果不合法直接no
        return false;

    sf(a, b, k);
    sf(x, y, k);//辗转除化简

    return (a == x && b == y);//返回结果
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int a0, a1, x, y, k;
        cin >> a0 >> a1 >> x >> y >> k;

        if (pd(a0, a1, x, y, k)) {
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }

    return 0;
}