Proper way of using Modulo operation

Question

In one of the programming contest, I was asked to take the Modulo with 1000000007.

Below is the code showing how I tried to achieve it.

#include <stdio.h>
#define ll long long
#define MOD 1000000007
ll getmin(ll a, ll b){return (a<b)?a:b;}

void solve(){
    ll a,b,c,Tv;
    scanf("%lld %lld %lld",&a,&b,&c);
    Tv = ((a%MOD)*(b%MOD)*(c%MOD))%MOD;
    ll sideofcube = getmin(a,getmin(b,c));
    ll numofcube = 0;
    ll smallvol = ((sideofcube%MOD)*(sideofcube%MOD)*(sideofcube%MOD))%MOD;
    numofcube = Tv/smallvol;
    printf("%lld %lld\n",sideofcube,numofcube);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        solve();
    }
    return 0;
}

With input

1
1000000000 1000000000 100000000

I get a negative response as

100000000 -1

What is going wrong here? I am taking MOD even before multiplying.

The problem with multiplication is that it usually overflows before you get a chance to apply to modulo operation. There have been answers for that already though. — harold, Apr 23 '17 at 12:39
Please do not do this `#define ll long long` - This will lead to lots of problems — Ed Heal, Apr 23 '17 at 12:39
... If just *must* have another name for `long long int` then use a `typedef long long int ll;` at least, to avoid macro related pitfalls — StoryTeller - Unslander Monica, Apr 23 '17 at 12:43
Macros are a blunt weapon. Any occurrence of `ll` will be replaced. It makes debugging more tricky. It makes reading of the code more difficult. Etc... (also ll looks like 11) — Ed Heal, Apr 23 '17 at 12:54

score 4 · Accepted Answer · edited Apr 23 '17 at 12:59

4

The product of ((a%MOD)*(b%MOD)*(c%MOD)) can overflow a 64 bit integer. To avoid this issue, only multiply two terms at a time:

    Tv = ((a % MOD) * (b % MOD)) % MOD;
    Tv = ((Tv) * (c % MOD)) % MOD;

Also you should use a typedef for ll:

typedef long long ll;

In this case, the product of two terms only needs 60 bits (log2(1000000007*1000000007)), so the product will not overflow and become negative. You might want to use a 64 bit unsigned integer (ull or uint64_t) since it could be faster on some systems.

edited Apr 23 '17 at 12:59

chqrlie

131,814
10
121
189

answered Apr 23 '17 at 12:48

rcgldr

27,407
3
36
61

Great explanation, thanks. Always feel good when I get to learn new concepts. One more doubt. In my code, I have also used "division". Is that a proper way to just divide directly when dealing with such "Modulo-fied" values ? – user3243499 Apr 23 '17 at 13:04
1

@user3243499 - for positive (or unsigned) numbers, the C or C++ remainder operator % is OK. To properly handle positive and negative numbers, if the remainder is not zero and it doesn't have the same sign as the divisor, add the divisor to the remainder. This produces a proper mathematical modulo, where the result is zero or has the same sign as the divisor. – rcgldr Apr 23 '17 at 13:12
@user3243499 - depending on the compiler, % by a constant may be implemented using a multiply and shift sequence instead of divide, but this is an internal detail. If interested, take a look at [multiply and shift to replace divide by constant](http://stackoverflow.com/questions/41183935/why-does-gcc-use-multiplication-by-a-strange-number-in-implementing-integer-divi/41224096#41224096) . – rcgldr Apr 23 '17 at 13:18

Proper way of using Modulo operation

1 Answers1