optimization for euclidean alghorithm c++

Question

The Euclidean algorithm works as follows:

1.Let a, b be the numbers whose GCD needs to be found.

2.If b = 0, then the number A is the desired GCD.

3.If b > a, then swap the numbers a and b.

4.Assign to the number a the value of a - b.

5.Return to step 2. Let's say we have numbers a, b, c, and d. It is required to determine whether, during the execution of the Euclidean algorithm for the given pair of numbers (a, b), there will be a moment when before performing step 2, the number a will be equal to c, and the number b will be equal to d.

Input The first line contains the number of sets of input data, k (1 ≤ k ≤ 100). Then follows the description of these sets. Each description consists of two lines. The first one contains two integers: a, b (1 ≤ a, b ≤ 10^18). The second line contains two integers: c, d (1 ≤ c, d ≤ 10^18). All numbers in the lines are separated by a space.

Output For each set of input data, output "YES" in a separate line if during the application of the Euclidean algorithm to the pair of numbers (a, b) at some point the pair (c, d) is obtained, or "NO" otherwise.

Max time is 1000ms.

my code that always failes after half of the tests because of the time limit.

#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;
}

Answer 1

Try something which involves a %= b; instead of a = a - b;, the former is much faster if a is much larger than b.

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;

        }
        if (b == d && c < a && (a - c) % b == 0) return true;
        a %= b;
    }
    return false;
}