Difference between __gcd and boost::math::lcm(a,b)

CodeChef-DSA-learners
1

I am using (a*b)/__gcd to find lcm in Appy and Contest and got 15 marks but by using boost::math::lcm(a,b) got full marks…
So please tell me waht is the difference between these two and where i was wrong…
My partially accepted solution.

1 Like
2

I think there might be an overflow here => (2 * n *__gcd(a,b)) when N and the gcd is large.

3

cout<<LLONG_MAX;
This statement prints the maximum value of long long int which in about 9 x 10^18.
In expression 2 x n x __gcd(a,b), n is of order 10^18 and __gcd(a,b) can be 10^9 maximum. Product is of order 10^27 . So overflow occurs.
You can also first calculate lcm and then divide n by it,
ll lcm=(a*b)/__gcd(a,b);

	ll tot=n/a + n/b - (2*(n/lcm));
2 Likes