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

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

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