在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）溢出如何影響模數？

回答

相關問題