c - 可能的路径[Hackerrank]编译超时

我已经在另一个编译器上尝试过我的代码，并且所有测试用例都能正常工作。不幸的是，hackerrank的编译器超时。任何人都可以提出一些建议来提高我的代码效率。

问题：
亚当站在无限的2D网格中的点（a，b）上。他想知道他是否可以到达点（x，y）。他唯一可以做的操作就是从某点（a，b）移至（a + b，b），（a，a + b），（a-b，b）或（a，a-b）点。假定他可以移动到此2D网格上的任意点，即具有正（或负）X（或Y）坐标的点。

告诉亚当他是否可以达到（x，y）。

我的代码：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>

long int GreatestCommonDivisor(long int a, long int b)
{
    long int div = 1;
    long int res;

    while ( div <= a)
    {
        if ((a % div == 0) && (b % div == 0)) res = div;
        div++;
    }
    return res;
}

int main() {
    int n, i;
    scanf("%d", &n);

    for (i = 0; i < n; i++)
    {
        long int a, b, x, y;
        scanf("%ld %ld %ld %ld", &a, &b, &x, &y);

        long int p1 = GreatestCommonDivisor(a, b);
        long int p2 = GreatestCommonDivisor(x ,y);

        if ( p1 == p2) printf("YES\n");
        else printf("NO\n");

    }
    return 0;
}

最佳答案

您需要一个更高效的算法：

#include <stdio.h>
#include <stdbool.h>

long int greatestCommonDivisor(long int m, long int n) {
    long int r;

    /* Check For Proper Input */
    if ((m == 0) || (n == 0))
        return 0;
    else if ((m < 0) || (n < 0))
        return -1;

    do {
        r = m % n;
        if (r == 0)
            break;
        m = n;
        n = r;
    }
    while (true);

    return n;
}

char *array[12];

int main() {
    int n, i;
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        long int a, b, x, y;
        scanf("%ld %ld %ld %ld", &a, &b, &x, &y);

        long int p1 = greatestCommonDivisor(a, b);
        long int p2 = greatestCommonDivisor(x, y);

        if (p1 == p2) array[i] = ("YES\n");
        else array[i] = ("NO\n");

    }
    for (i = 0; i < n; i++) {
        printf("%s", array[i]);

    }
    return 0;
}

您的原始版本也未通过输出测试，因此必须对其进行格式化。