MahmoudSayed's blog

I need a help, please.

By MahmoudSayed, 10 years ago, In English

I have 3 numbers A, B, and C. where A = 97830131475, B = 587117 and C = 109546051211. `I wanna get A * B (mod C) without overflow using c++. I used this formula:

     unsigned long long x = A % C * B % C;
     x %= C;

but still getting overflow. where x = 0. can someone help me!! Thanks in advance. :)

Tags c++
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Since C > 232, the product of two numbers might exceed the range of a long long even if you take both numbers mod C first. You could get around this with the following algorithm:

long long multiply(long long A, long long B, long long MOD)
{
    if (B == 0) return 0;
    if (B % 2 == 1) return (A + multiply(A, B-1, MOD)) % MOD;
    long long partial = multiply(A, B / 2, MOD);
    return (partial + partial) % MOD;
}

However, it won't help you in this case because you're already getting the correct answer. 97830131475·587117 = 109546051211·524325.

→ Reply