在C++中int（或long long）溢出如何影响模数？

假设我有两个long long，a和b，我需要相乘，然后得到值k对于一些大的k，这样a，b和k都在long long的范围内，但不是int 。为简单起见，a，b < k。在C++中int（或long long）溢出如何影响模数？

因此，代码将是：

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

然而，因为a，b是如此之大，如果乘像上面，并且溢出和变为负，则模k将是一个负数和不正确。

如何确保值mod k是正确的？

编辑：作为奖金，这是如何在Java中工作？是否如预期的那样？还是BigInteger需要？

来源

2015-06-14 John Targaryen

查看http://stackoverflow.com/questions/4240748/allowing-signed-integer-overflows-in-c-c – juanchopanza

a，b nneonneo

尝试使用（a * b）％k ==（（a％k）*（b％k））％k的事实。如果k小于long，这将起作用。如果没有，你将需要做一些简单的多精度。 –

许多编译器都提供了128位整数类型。例如，g++你可以做一个函数

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

旁白：如果可以的话，尽量坚持到无符号整数类型时，你在做模运算。整数除法的舍入行为使得在涉及有符号值时使用%非常尴尬。

来源

2015-06-14 22:08:05 Hurkyl

如果你知道的值都小于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

如果你的数字比这更大的，你需要去图书馆多倍如GMP

来源

2015-06-14 22:01:17

一次一点意味着一个额外的log（n）乘法因子？ –

由于这里可能的最大尺寸是63或127位（取决于机器上长整型的大小），因此不适用渐近表达式。 –

在C++中int（或long long）溢出如何影响模数？

回答

相关问题