Finding (a*b)/c % m

general
,
1

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
2

Read about,

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

Thank You

1 Like
4

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

5

Modular exponential

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

2 Likes
6

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

1 Like
7

'[ (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
8

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

1 Like
9

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

10

Read this for finding modular inverses in logarithmic time

1 Like
11

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
12

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
13

Thanks Brother :heart:

2 Likes
15

Wait , is this from some ongoing challenge ?

16

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

17

share link of problem from SPOJ .

18

here you go.

19

This will help u.