LCM和GCD不能正常工作

我编写了一个codechef程序和它的错误（虽然所有的测试都是正面的）。代码是：LCM和GCD不能正常工作

#include <iostream> 
using namespace std; 

int g (int a,int b){ 
    return b == 0 ? a : g(b, a % b); 
} 

int l (int a, int b){ 
    return (a*b)/(g(a,b)); 
} 

int main() { 
    int n; 
    cin >> n; 
    int a[n],b[n]; 
    for (int x = 0;x<n;x++){ 
     cin >> a[x] >> b[x];  
    } 
    for (int x = 0;x<n;x++){ 
     cout << g(a[x],b[x]) << " "<< l(a[x],b[x]) << endl; 
    } 

    return 0; 
}

Codechef不会告诉我什么整数不工作，我敢肯定我的gcd功能是合法的。

来源

2017-07-18 Jayylmao

你有没有考虑过'a'和/或'b'接近INT_MAX会发生什么？ – Frank

你的意思是“它的错误显然（尽管所有的测试都是正面的）”？为什么它错了？哪些测试“积极”？请提供有关您遇到的具体问题的更多详细信息。 –

@Frank该问题的参数在int max下。 – Jayylmao

由于gcd正确定义为最大的非负的最大公约数，就可以保存自己恼人的细节签署了划分，例如，

static unsigned gcd (unsigned a, unsigned b) 
{ 
    /* additional iteration if (a < b) : */ 
    for (unsigned t = 0; (t = b) != 0; a = t) 
     b = a % b; 

    return a; 
}

同样的lcm;但这里的问题是(a*b)可能溢出。因此，如果您有两个大的（有符号的）共素数的int值，例如：2147483647和2147483629，则gcd(a,b) == 1和(a*b)/g溢出。

在大多数平台上的一个合理假设是unsigned long long是unsigned的宽度的两倍 - 尽管严格来说并不一定如此。这也是使用确切类型的一个很好的理由，如[u]int32_t和[u]int64_t。

您可以确定的一件事是a/g或b/g不会导致任何issues。因此，一个可能的实现可能是：

static unsigned long long lcm (unsigned a, unsigned b) 
{ 
    return ((unsigned long long) a) * (b/gcd(a, b))); 
}

如果测试值是“积极的”（这是我想你的意思），你可以先投他们打电话之前(unsigned)。更好的是 - 用unsigned int替换你所有的int变量（尽管循环变量很好），并且省去了麻烦。

来源

2017-07-19 03:22:56

谢谢，那修好了！ – Jayylmao

LCM和GCD不能正常工作

回答

相关问题