python - 如何将此 Python 代码转换为 C++

Question

我在 Python 中有一个工作算法，我想将其转换为 C++:

def gcd(a, b):    
    if (a % b == 0):
        return b
    else:
        return gcd(b, a % b)

def solution(N, M):
    lcm = N * M / gcd(N, M)
    return lcm / M

我遇到大输入值的问题，因为 N 和 M 的倍数导致整数溢出，使用 long 来存储它的值似乎没有帮助，除非我正在做某事错了。

这是我当前的代码:

int gcd(int a, int b)
{
    if (a % b == 0)
        return b;
    else
        return gcd(b, a % b);
}

int solution(int N, int M) {

    // Calculate greatest common divisor
    int g = gcd(N, M);

    // Calculate the least common multiple
    long m = N * M;
    int lcm = m / g;

    return lcm / M;
}

Answer 1

您正在计算 g=gcd(N,M)，然后是 m=N*M，然后是 lcm=m/g，最后返回 lcm/M。这与返回 N/gcd(N,M) 相同。您不需要那些中间计算。摆脱他们。现在溢出没有问题(除非 M=0，也就是说，您没有防止溢出)。

int solution(int N, int M) {
   if (M == 0) {
      handle_error();
   }
   else {
      return N / gcd(N,M);
   }
}