Geek Answers Handbook

How does int (or long long) overflow in C ++ affect a module?

Suppose I have two long longs, a and b, which I need to multiply, then get the mod k value for some big k, so that a, b and k are all in the range of long long, but not inner. For simplicity, a, b <k.

Thus, the code will look like this:

long long a, b, k;
cin >> a >> b >> k;
cout << (a * b)%k << "\n";

However, since a and b are so large, if you multiply as above and it overflows and becomes negative, then mod k will be a negative number and incorrect.

How can you guarantee the correct mod k value?

Edit: as a bonus, how does it work in Java? Is this the same as expected? Or do you need BigInteger?

+4
source share
2

128- . , g++

static inline int64_t mulmod(int64_t x, int64_t y, int64_t m)
{
    return ( (__int128_t)x * y) % m;
}

: , , . % , .

+1

, ULONGLONG_MAX/2 ( ), :

unsigned long long mulmod(unsigned long long a, unsigned long unsigned long b, long long m) {
    unsigned long long rv = 0;
    a %= m;
    b %= m;
    while (b) {
        if (b&1) { rv += a; if (rv >= m) rv -= m; }
        a += a; if (a >= m) a -= m;
        b >>= 1; }
    return rv; }

, gcc/x86_64, :

unsigned long mulmod(unsigned long a, unsigned long b, unsigned long m) {
    unsigned long rv;
    asm ("mulq %2; divq %3" : "=d"(rv), "+a"(a): "S"(b), "c"(m));
    return rv;
}

ULONG_MAX

, multiprecision, ​​ GMP

+1

More articles:


All Articles