查一系列大整数的LCM时如何避免溢出错误(How to avoid overflow error when finding LCM for series of large integers)

查一系列大整数的LCM时如何避免溢出错误(How to avoid overflow error when finding LCM for series of large integers)

我需要到一系列数字的最小公约数（最多10万个数字，每个数字在[0,2 000 000 000]范围内）

我使用以下算法lcm（a，b）=（a / gcd（a，b））* b

到1cm以上的lcm（a，lcm（b，c））...的标准方法适用于小输入值。

但是，对于大输入，即使我使用long long int，它也会开始出现溢出错误...

如何避免许多较大整数值出现溢出错误？

感谢您的帮助

I need to find least common divisor for a series of numbers (up to 100 000 numbers, each of them is in the range of [0, 2 000 000 000])

I am using the following algorithm lcm(a,b) = (a/gcd(a,b)) * b

The standard method of finding lcm for for than 2 numbers lcm(a, lcm(b,c))... is working for small input values.

However, for large input, it starts giving overflow error even if i used long long int...

How can I avoid having overflow error for many larger integer values?

Thank you for the help

最满意答案

在这种情况下，最小公倍数可以是具有数百个数字的大数。 你需要处理这么大的整数。

gmplib库 （ -lgmp ）支持任意精度整数运算：

int have_read_first_number = 0; mpz_t result, arg; mpz_inits(result, arg, ULL); 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 -o lcm -lgmp && { seq 1 100 | ./lcm; } 6972075229712477164580895120556800

完整程序：

Least common multiple in this case can be a large number with hundreds of digits. You need to handle such big integers.

gmplib library (-lgmp) supports arbitrary precision integer arithmetic:

int have_read_first_number = 0; mpz_t result, arg; mpz_inits(result, arg, ULL); 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("");

Example:

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

Complete program: