如何计算形如(a*b)%c的模数？

Question

如何计算形如（a*b）%c 的模数？

我想要计算两个整数相乘的模数，其中它们几乎接近溢出的阶段......

这里的c也是整数类型。

- Kunal

Answer 1

(a * b) % c == ((a % c) * (b % c)) % c

- kennytm

---

+1 刚刚已经评论过了，但是因为缺乏咖啡所以不太确定。 ;) - Bart

如果 a <= b < c，则 a % c 和 b % c 将不起作用，因此我们仍然可能会得到溢出。 - Westy92

Answer 2

< p>那么((a % c) * (b % c)) % c呢？根据您的架构，这可能比转换为更大的类型更快或更慢。

- Mark B

---

如果满足 a <= b < c，则 a % c 和 b % c 不会有任何作用，因此我们仍然可能会发生溢出。 - Westy92

Answer 3

你可以将a和c转换为long long，这样乘法就不会溢出。

((long long)a * (long long)b) % c

- buc

---

我需要一种优化的方法。 - Kunal

我认为你不会找到更快的解决方案。在x86机器上，32位乘法的结果总是64位。这样，你只需通知编译器使用64位结果即可。 - buc

长长整型并不总是比整型大（尤其是在现代计算机上）。 - Martin York