2长长整数的LCM

问题描述：

我想计算长1长整数尽可能快。2长长整数的LCM

对于离 A = 10^18 B = 10^17

我正在做LCM（A，B）= A * B/GCD（A，B）为整数但对于长长的会有溢出

应该是什么最快的方法来计算它？

为什么不'a *（b/gcd（a，b））'？ – 2012-04-02 01:38:44

您是否有效地询问“我何时需要使用'多精度'库，以及如何最好地利用'long long'来避免这种开销”？或者你有一些值溢出可以吗？ – gbulmer 2012-04-02 01:49:15

答

你总是会遇到溢出问题，特别是当你有大的副数时。但为了弥补这一点，你可以像迈克尔建议的那样写a * (b/gcd(a,b))。由于gcd(a,b)是a和b的除数，所以不用担心由于整数除法导致的结果不准确。

答

a*b <= c 
// When will a*b overflow c? 
a > c/b

在你的情况下，c可以是LLONG_MAX。