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)
- (ab)%m = ((a%m)(b%m))%m for proof and
- Modular division + multiplicative inverse
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.
'[ (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…
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.