CODEWITHSUNDEEP
c++modulointeger-overflow
Falconal
Falconal

Reputation: 67

Avoid int overflow when doing a large multiplication

I'm training to participate in a programming contest, so I'm trying to get used to the common things in that kind of problems. I've been having problems with something in particular: int overflow due to insanely big numbers, there's this particular problem I would like to know how to solve: Amelia and Rabbit Island. This is my code:

#include <iostream>

int main(){

   unsigned long long int a,b,c;
   int t;

   int nweeks;

   std::cin >> t;

   int **lines = new int*[t];
   for (size_t i = 0;i<t;i++)
      lines[i] = new int[3];

   for(size_t i=0;i<t;i++)
      for(size_t j=0;j<3;j++)
         std::cin >> lines[i][j];  


   for (size_t i=0;i<t;i++){
      a = lines[i][1];
      b = lines[i][2];
      const unsigned int mod = 1000000;
      for (size_t j=0;j<lines[i][0] - 2;j++){

         if (j > 0){
            c = a;
            a = a * b % mod;
            b = c;

         }
         else {
            a = a * b;
         }
      }

      nweeks = (lines[i][0] * 3) - 2;

      std::cout << "At week " << nweeks << " we obtain " << a%mod << " new rabbits.\n";
   }


   for (size_t i=0;i<t;i++)
      delete[] lines[i];

   delete[] lines;
   return 0;
}

In the problem it says that the answer must be expressed in mod(1000000), this is supposed to avoid the overflow, but I just can't find the way to make it work, my solution works for normal values, but for example the specific case of the input:

1 1000 10 10

That is the maximum allowed input for a single case, the output I get is:

At week 2998 we obtain 0 new rabbits. Which is wrong, all because the int overflowing in multiplication.

Thanks in advance.

EDIT: Well, for some reason the evaluator system now accepts mi solution -.-, thanks anyway.

Upvotes: 0

Views: 95

Answers (1)

R Sahu
R Sahu

Reputation: 206717

You have unfortunate selection of input.

If you add couple of lines to output a and b as the last lines of the for loop,

std::cout << "a: " << a << "\n";
std::cout << "b: " << b << "\n";

you can trace how the values of a and b change.

By using 1 10 10 10 as input, I get the following output:

a: 100
b: 10
a: 1000
b: 100
a: 100000
b: 1000
a: 0
b: 100000
a: 0
b: 0
a: 0
b: 0
a: 0
b: 0
a: 0
b: 0
At week 28 we obtain 0 new rabbits.

After that, a and b will continue to be zero. The answer is not incorrect. The output modulus 100000 is indeed zero.

By using 1 10 8 8 as input, I get the following output:

a: 64
b: 8
a: 512
b: 64
a: 32768
b: 512
a: 777216
b: 32768
a: 813888
b: 777216
a: 775808
b: 813888
a: 821504
b: 775808
a: 375232
b: 821504
At week 28 we obtain 375232 new rabbits.

which look more acceptable even though both sets of results are correct.

Upvotes: 1

Related Questions