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

Question

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

Я использую следующий алгоритм lcm(a,b) = (a/gcd(a,b)) * b

Стандартный метод поиска lcm для более чем 2 чисел lcm (a, lcm (b, c))... работает для небольших входных значений.

Тем не менее, для большого ввода, он начинает выдавать ошибку переполнения, даже если я использовал long long int...

Как можно избежать ошибки переполнения для многих больших целых значений?

Спасибо вам за помощь

Answer 1

Наименьшее общее кратное в этом случае может быть большим числом с сотнями цифр. Вам нужно обрабатывать такие большие целые числа.

gmplib библиотека (-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

Полная программа:lcm.c