如何避免當找到一系列大整數的LCM時發生溢出錯誤

Question

我需要爲一系列數字 找到最小公約數（最多100 000個數字，每個數字都在[0，2 000 000 000]）

我使用以下算法LCM（A，b）=（A/GCD（A，b））* b

找到LCM爲大於2的數字LCM的標準方法（一，lcm（b，c））...正在處理小的輸入值。

然而，對於較大的輸入，它開始給溢出錯誤，即使我用很長很長...... INT

我怎樣才能避免爲許多較大的整數溢出錯誤？

感謝您的幫助

Answer 1

最小公倍數在這種情況下，可以將大量有數以百計的數字。你需要處理這樣的大整數。

gmplib library（-lgmp）支持任意精度整數運算：

int have_read_first_number = 0; 
mpz_t result, arg; 
mpz_inits(result, arg, NULL); 
mpz_set_ui(arg, 1u); 

/* read decimal integers from stdin: one per line */ 
while((len = getline(&token, &capacity, stdin)) > 0) { 
    if (!have_read_first_number) { /* read the first integer */ 
    parse_mpz(token, result); 
    have_read_first_number = 1; /* successfully read first integer */ 
    } 
    else { /* read the rest of the numbers */ 
    parse_mpz(token, arg); 
    } 
    /* lcm(a, b, c, d) = lcm(lcm(lcm(a, b), c), d) */ 
    mpz_lcm(result, result, arg); 
} 
if (!have_read_first_number) /* error */ 
    panic("no numbers read"); 

/* print result as decimal */ 
mpz_out_str(stdout, 10, result); 
puts(""); 

實施例：

$ gcc lcm.c -o lcm -lgmp && { seq 1 100 | ./lcm; } 
69720375229712477164533808935312303556800 

Complete program: lcm.c