very strange mod operation overflow. Pls help

general
, ,
1

int ans,sum;

the variable sum is generated everytime(it is the sum of values in each column of the 2d array, and ans is the product of all the sums) and is basically small value, I am getting AC for the following codes :

ans=( (ans%mod) * (sum) ) %mod ;

ans=( (ans) * (sum%mod) ) %mod ;

but getting wrong answer for:

ans=(ans*sum)%mod;

question

solution

pls someone help me with this

2

It’s probably just as you say: ans*sum is simply too big to store, so it overflows. This can happen even if ans and sum are small enough to be ints because int multiplication yields int, even if it should yield a long long. Here’s an example of this:


#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int main() {
    long long m = (long long)pow(2, 31), m2 = m+1;
    int n = (int)pow(2, 31), n2 = n+1;
    printf("%lli %lli", n*n2, m*m2);
    exit(0);
}

This first product of ints should yield an incorrect product from overflow while the product of long longs yields the right answer even though in printf(), we asked for long longs from both products.

This is probably what happened in this problem: ans and sum were small enough to be regular ints, but too big to multiply together into an int. To stop this from happening, keep taking the % mod of one or both of the multiplicands before multiplying big ints together.

1 Like
3

I am able to understand what you are trying to tell, so now one more question… where is the result of n*n2 stored?? what is the data type in which it is stored??

4

please explain, I am able to understand what you are trying to tell, so now one more question… where is the result of n*n2 stored?? what is the data type in which it is stored??

5

Because n*n2 is a product of ints, and it is stored somewhere as an int. I don’t know where exactly it is stored, but I would guess that the compiler would store it as an int somewhere temporarily.