Как избежать ошибки переполнения при поиске LCM для серии больших целых чисел

Question

Мне нужно найти наименьший общий делитель для ряда чисел (до 100 000 номеров, каждый из которых находится в диапазоне [0, 2 000 000 000])

Я использую следующий алгоритм LCM (а, б) = (A/НОД (а, б)) * б

стандартный метод нахождения 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