我需要找到一系列数字的最小公除数(最多100000个数字,每个数字在[0,2000000000000]范围内)
我正在使用以下算法lcm(a,b)=(a / gcd(a,b))* b
查找2个以上的数字lcm(a,lcm(b,c))...的lcm的标准方法适用于较小的输入值。
但是,对于大输入,即使我使用了很长很长的时间,它也会开始产生溢出错误...
如何避免许多较大的整数值出现溢出错误?
感谢您的帮助
在这种情况下,最小公倍数可以是具有数百个数字的大量数字。您需要处理这么大的整数。
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
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句