Today we will solve this problem, of finding modulo of huge numbers, which we face frequently in our CP world.

For now I can remember only one problem on codechef which needs this. Comment down if you know some other problems.

Lets see the modulo operation first. We will have a quick look since we already have discussed about Modular Arithmetic in good detail.

It is a distributive over addition, multiplication. i.e.

1. (A+B)%m = (A%m + B%m) %m

2. (A*B)%m = (A%m * B%m) %m

These two will help here, mainly the first one.

Consider, 'abcdepqr' is a string of digits, ok?

Is not abcdepqr = (abcde*1000 + pqr) ? Yes, it is.

Similarly, (a*10000000 + bcdepqr), right?

This is the thing we are going to apply.

What will we do is,

1. Get one variable to store the answer intialized to zero.

2. Scan the string from left to right,

3. Everytime multiply the answer by 10 and add the next number and take the modulo and store this as new answer.

E.g. 12345 % 100:
ans = 0
ans = (o*10 + 1)%100
ans = (1*10 + 2)%100
ans = (12*10 + 3)%100
ans = (23*10 + 4)%100
ans = (34*10 + 5)%100
ans = 45.

It means: we, at the end, are doing this only:

a*10000000 + b*1000000 + c*100000 + d*10000 + e*1000 + p*100 + q*10 + r

which is nothing but 'abcdepqr'!

This way have proved the correctness too.

I think you have got it!

This will solve the problem.

I hope you like this post, have look at my other notes here.