I am calculating Lcm using gcd. But a and b are big and its overflowing. Any idea how to solve it ? (I am using cpp)

Read about,

- (a
*b)%m = ((a%m)*(b%m))%m for proof and - Modular division + multiplicative inverse

Thank You

Can you say how to use mod calculating pow(a,b);

This article should answer your query. Let me know if I did not answer your query correctly.

Yes, Thats the right approach. Use the link for Modular exp provided by arnabsinha

@faysal_795

'[ (a * b ) / c ] % m = ( (a % m) * (b % m) )%m * (c^{-1}%m)

=> ( ( (a % m) * (b % m) )%m * (pow(c , m-2 , m) ) ) %m

Also, one great learning is pow(a, b) can be calculated in (log n) time complexity, whether or not mod is involved.

The simplification is cool, I use Extended euclid algorithm to find multiplicative inverse and substitute.

Read this for finding modular inverses in logarithmic time

For example …jaise a aur b ka lcm nikalna hai…a ke factor 2^3 hai aur b ke factor 2^5 hai to hum log lcm me 2^5 factor ko lete hai jo jyada hai…isi concept ko use krke mod karne pe ho jaega…

If m is prime you can use ((a%m)*(b%m)%m)*pow(c, m-2, m)%m , else you need Euler’s Theorem to find c^(-1) modulo m…

Thanks Brother

Wait , is this from some ongoing challenge ?

Not that i am aware of. I was trying spoj (LCM sum) problem. If its in current ongoing contest, let me know. I will delete the post.

Thanks in advance

share link of problem from SPOJ .

here you go.