Mod operator

general
, , ,
1

what i am trying to do is res[x]=res[x-1]+res[x-1]+cnt
where cnt=cnt*2;
cnt begins at 1.
x can be as large as 1000000
i need to o/p the answer as %1000000007

what m doing is res[x]=(res[x-1]+res[x-1]+cnt)%MOD
cnt=(cnt*2)%MOD
this isn’t the right approach probably, everytime i see the MOD operator I always get a nervous break down. Is there any specific approach to solve the problems involving MOD operator??

Please Help!!

3 Likes
2

That quite depends upon the problem statement. You might come across different situations where even finding modulo itself needs an algorithm to be efficient enough to solve the problem. For God’s sake, we have some good and popular algorithms which make the work for us.
Few of them are

  • Fermat’s little theorem
  • Fast Modular Exponentiation
  • Modular multiplicative inverse
which you might find useful for solving most the problems involving Modulo operation for large numbers.
Here are some useful links for you to get started
http://en.wikipedia.org/wiki/Fermat%27s_little_theorem
http://en.wikipedia.org/wiki/Modular_exponentiation
http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

Once you got to feel comfortable with the actual algorithm, try to implement them in your preferred language.


Some problems may include much complex logics behind to solve modularity. But, try to have a good understanding of the problem before actually worrying about the coding.

3 Likes
3

Here overflow may occur so try to module MOD by each variable.

(a * b) % MOD is same as ( (a % MOD) * (b % MOD) ) % MOD

and

(a + b) % MOD is same as ( (a % MOD) + (b % MOD) ) % MOD
So

For this expression, res[x]=res[x-1]+res[x-1]+cnt

Perform this operation

res[x] = ( (res[x-1] % MOD) + (res[x-1] % MOD) + (cnt % MOD) ) % MOD;

1 Like
4

I have seen your former question about (a/b)%c != (a)%c/b. This needs to be solved using Modular Multiplicative Inverse and hence updated my answer :slight_smile: @apurvjain17

5

But for division rules are different.