LCM und GCD funktioniert nicht

Question

Ich habe ein Programm für Codechef und seine falsche apparently (obwohl alle Tests positiv waren). Der Code ist:

#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 mir nicht sagen, welche ganzen Zahlen arbeiten nicht, und im ziemlich sicher, dass meine gcd Funktion echt ist.

Answer 1

Da gcd richtig als das größte nicht-negativen gemeinsamen Teiler definiert ist, können Sie sich die lästigen Details signierter Division speichern, zum Beispiel

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; 
} 

Ebenso für lcm; aber das Problem hier ist, dass (a*b) überlaufen kann. Wenn Sie also zwei große (vorzeichenbehaftete) int-Werte haben, die co-prime sind, sagen Sie: 2147483647 und 2147483629, dann gcd(a,b) == 1 und (a*b)/g Überläufe.

Eine vernünftige Annahme auf den meisten Plattformen ist, dass unsigned long long ist doppelt so breit wie unsigned - obwohl genau gesagt, muss es nicht sein. Dies ist auch ein guter Grund, exakte Typen wie [u]int32_t und [u]int64_t zu verwenden.

Eine Sache, der Sie sicher sein können ist, dass a/g oder b/g keine issues verursachen wird. So eine mögliche Implementierung könnte sein:

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

Wenn Ihre Testwerte sind ‚positiv‘ (das ist, was ich denke du meinst), können Sie sie vor (unsigned) werfen kann vor rufen. Besser noch - ersetzen Sie alle Ihre int Variablen durch unsigned int (obwohl die Loop-Variablen sind in Ordnung), und ersparen Sie sich die Schwierigkeiten, damit zu beginnen.