2長長整數的LCM

Question

我想計算長1長整數儘可能快。

對於離 A = 10^18 B = 10^17

我正在做LCM（A，B）= A * B/GCD（A，B）爲整數 但對於長長的會有溢出

應該是什麼最快的方法來計算它？

Answer 1

你總是會遇到溢出問題，特別是當你有大的副數時。但爲了彌補這一點，你可以像邁克爾建議的那樣寫a * (b/gcd(a,b))。由於gcd(a,b)是a和b的除數，所以不用擔心由於整數除法導致的結果不準確。

Answer 2

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

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