C++ Handling Large Integer Values

Iam new to Codechef . I don’t know how to handle very large integer values .
The Problems given usually have large no’s like 10^10 . I have seen the use of Mod but couldn’t understand it well .

u need to know modular arithmetic. if you use MOD cleverly u can get rid of integer over flow.

First go through this LINK

What is clever here??
=> some time using (a**b)%MOD won’t work because system calculates aXb first if that leads to an interger overflow then we will end up in wrong answers
so it will be better to use ((a%MOD)*(b%MOD))%MOD

Same rule follows everywhere whenever there is a chance of integer overflow break it and apply MOD and then organize the equation accordingly.These rules can be found in the link.

Most of this , you will get through practice.

Happy Coding

1 Like

No ,I don’t want to use any long long datatype . The Problems given will be given out of range of long long datatype . I want to use Modular Arithmetic for this .

No ,I don’t want to use any long long datatype . The Problems given will be given out of range of long long datatype . I want to use Modular Arithmetic for this .

Hello,

Well, if you don’t want to use native language data-types, I am assuming that you are interested in solving problems such that the intermediate calculations are small, but, final results tend to be very large, like computing a factorial of a big number, or perform some huge exponentiation like 16^5000 or so.

The “trick” behind these sort of problems is that you can use what is known as a modular value such that the value computed is actually the remainder of the answer when you divide it by the modulo value.

So, to compute 16^5000 MOD 1000000007 is to compute the remainder of the answer 16^5000 / 1000000007.

The idea is that the MOD operator is, in a sense, comulative, i.e., you can iteratively do:

answer = 1
for i = 1 to 5000
answer = (answer * 16) MOD 1000000007
print answer MOD 1000000007

Like this, you ensure that the values involved in your intermediate calculations never exceed 1000000007 and also that the final result is well computed.

This is a widely used trick, both to avoid computing large values and also to introduce people to how Modular Arithmetic works.

Hope this helps you.

Best,

Bruno

3 Likes

updated my answer then :slight_smile:

Thanks for the Help .Understood it well.

Thanks for the Help .Understood it well.