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不能正常工作

回答

相關問題