c++ 中的 int(或 long long)溢出如何影响模数?
How does int(or long long) overflow in c++ affect modulus?
假设我有两个long long,a和b,我需要相乘,然后得到一些大k的值mod k,这样a,b和k都在范围内long long 但不是 int。为简单起见,a, b < k.
因此代码将是:
long long a, b, k;
cin >> a >> b >> k;
cout << (a * b)%k << "\n";
但是a和b太大了,如果像上面那样相乘,溢出变成负数,那么modk就是负数,不正确。
如何确保 mod k 的值是正确的?
编辑:作为奖励,这在 Java 中如何运作?是不是和预想的一样?还是需要 BigInteger?
如果您知道值小于 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
许多编译器提供 128 位整数类型。例如,使用 g++
你可以创建一个函数
static inline int64_t mulmod(int64_t x, int64_t y, int64_t m)
{
return ( (__int128_t)x * y) % m;
}
旁白:如果可以的话,在进行模运算时尽量坚持使用无符号整数类型。整数除法的舍入行为使得在涉及有符号值时使用 %
非常尴尬。
假设我有两个long long,a和b,我需要相乘,然后得到一些大k的值mod k,这样a,b和k都在范围内long long 但不是 int。为简单起见,a, b < k.
因此代码将是:
long long a, b, k;
cin >> a >> b >> k;
cout << (a * b)%k << "\n";
但是a和b太大了,如果像上面那样相乘,溢出变成负数,那么modk就是负数,不正确。
如何确保 mod k 的值是正确的?
编辑:作为奖励,这在 Java 中如何运作?是不是和预想的一样?还是需要 BigInteger?
如果您知道值小于 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
许多编译器提供 128 位整数类型。例如,使用 g++
你可以创建一个函数
static inline int64_t mulmod(int64_t x, int64_t y, int64_t m)
{
return ( (__int128_t)x * y) % m;
}
旁白:如果可以的话,在进行模运算时尽量坚持使用无符号整数类型。整数除法的舍入行为使得在涉及有符号值时使用 %
非常尴尬。