欧几里得算法C++代码超时求助：优化指定数对出现判断逻辑

欧几里得算法执行步骤如下：

1. 设a、b为需求解最大公约数（GCD）的两个数。
2. 若b=0，则a即为所求的GCD。
3. 若b>a，则交换a和b。
4. 将a赋值为a - b。
5. 返回步骤2。

需实现功能：给定四个整数a、b、c、d，判断在对(a,b)执行上述欧几里得算法的过程中，是否存在某个时刻（执行步骤2前），a等于c且b等于d。

• 输入：第一行输入测试用例组数k（1≤k≤100），每组用例含两行，第一行是a、b（1≤a,b≤10^{18），第二行是c、d（1≤c,d≤10}18），数字以空格分隔。
• 输出：每组用例输出"YES"或"NO"，表示是否出现指定数对。
• 时间限制：1000ms。

编写的C++代码在半数测试用例后因超时失败，代码如下：

#include <iostream>

using namespace std;

bool checkEuclideanAlgorithm(long a, long b, long c, long d) {

    int temp;
    while (b != 0) {

        if (a == c && b == d)
            return true;
        if (b > a) {
            temp = a;
            a = b;
            b = temp;

        }
        a = a - b;
    }

        return false;
}


int main() {
    int k;
    cin >> k;
    long long a, b, c, d;

    for (int i = 0; i < k; ++i) {

        cin >> a >> b >> c >> d;
        if (checkEuclideanAlgorithm(a, b, c, d))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

请求优化该代码以通过全部测试用例。

核心思路 #

原代码超时的根源是逐次减法导致循环次数爆炸：当a远大于b时（比如a=1e18、b=1），需要循环1e18次，完全超出时间限制。优化思路是用除法批量计算可减去的次数，直接跳步减少迭代；同时增加前置校验过滤无效情况。

优化后的代码 #

#include <iostream>
#include <algorithm>

using namespace std;

long long gcd(long long x, long long y) {
    while (y != 0) {
        long long temp = y;
        y = x % y;
        x = temp;
    }
    return x;
}

bool checkEuclideanAlgorithm(long long a, long long b, long long c, long long d) {
    // 前置校验：目标数对的GCD必须与原始数对一致，否则直接排除
    long long gcd_ab = gcd(a, b);
    long long gcd_cd = gcd(c, d);
    if (gcd_ab != gcd_cd) {
        return false;
    }

    while (b != 0) {
        // 检查当前状态是否匹配目标
        if (a == c && b == d) {
            return true;
        }
        // 处理b>a的情况：交换前先检查是否匹配目标
        if (b > a) {
            if (b == c && a == d) {
                return true;
            }
            swap(a, b);
            continue;
        }
        // 若当前a小于d，后续减法只会让a更小，无法到达目标，直接退出
        if (a < d) {
            break;
        }
        // 检查是否可以通过一次批量减法到达目标
        if (b == d && c <= a && (a - c) % b == 0) {
            return true;
        }
        // 计算最大可批量减去的次数，避免跳过目标
        long long n = a / b;
        if (a - n * b < d) {
            n = (a - d) / b;
            n = max(n, 1LL);
        }
        a -= n * b;
    }
    // 检查循环结束前的最后状态
    return (a == c && b == d);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加速IO，避免输入输出耗时超时

    int k;
    cin >> k;
    long long a, b, c, d;
    for (int i = 0; i < k; ++i) {
        cin >> a >> b;
        cin >> c >> d;
        cout << (checkEuclideanAlgorithm(a, b, c, d) ? "YES\n" : "NO\n");
    }
    return 0;
}

关键优化点说明 #

1. GCD前置校验：算法过程中所有数对的GCD保持不变，若(c,d)的GCD与(a,b)不同，直接返回NO，避免无效循环。
2. 批量减法：用除法计算n = a/b，一次性减去n*b，将循环复杂度从O(a/b)降至O(log(max(a,b)))，满足1000ms时间限制。
3. 边界状态检查：处理交换前后的状态，以及避免跳过目标数对的情况，确保不会遗漏匹配机会。
4. IO加速：添加ios::sync_with_stdio(false); cin.tie(nullptr);减少输入输出的系统调用耗时，适配大数据量输入。

内容的提问来源于stack exchange，提问作者degwar