如何使这种线性时间复杂度变为对数时间复杂度？

Question

我正在练习编码挑战，但遇到了这个问题。

A和他的朋友在整数商店各买了一个数，A有N号，他的朋友有M号。A希望他们的两个数互质。为此，A 将这两个数字除以可以整除这两个数字的最大数字。 A做完这个操作想知道数字的和，帮他求那个和。

输入

Input: 
N = 6, M = 5
Output: 
11
Explanation:
The largest number that can divide both 
5 and 6 is 1. 
After dividing, 5+6 = 11.

我试过这个代码

long sum(long N, long M){
    long divider = 1;
    long min = Math.min(N,M);
    for(long i=2; i<=min; i++)
        if(N%i==0 && M%i==0)
            divider=i;
    return (N/divider) + (M/divider);
}

但预期的运行时间复杂度为 O(log(n))。但是我的代码给出了 O(n).

我找不到任何方法使其对数。请帮助我。

Answer 1

您应该使用任何有效的算法来找到 GCD - 最大公约数。例如。您可以尝试使用 O(log(min(N, M)) 时间复杂度 Euclidean algorithm。

public static long sum(long N, long M) {
    long gcd = gcdEuclideanAlgorithm(N, M);
    return (N / gcd) + (M / gcd);
}

private static long gcdEuclideanAlgorithm(long a, long b) {
    return b == 0 ? a : gcdEuclideanAlgorithm(b, a % b);
}

您可以找到更多算法 here。

如何使这种线性时间复杂度变为对数时间复杂度？

How to make this linear time complexity to log time complexity?

java

performance

time