Finding (a*b)/c % m

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)

1 Like

Read about,

  1. (ab)%m = ((a%m)(b%m))%m for proof and
  2. Modular division + multiplicative inverse
1 Like

Thank You

1 Like

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

Modular exponential

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

2 Likes

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

1 Like

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

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

4 Likes

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

1 Like

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


Read this for finding modular inverses in logarithmic time
1 Like

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…

1 Like

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…

2 Likes

Thanks Brother :heart:

2 Likes

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.

This will help u.