Блог пользователя MahmoudSayed

I need a help, please.

Автор MahmoudSayed, 9 лет назад, По-английски

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. :)

Теги c++
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить