c - 如何在c中获取 (3623752876 * 3623752876) % 4294434817

Question

我实现了一种快速幂算法来执行操作(x^y) % m。

由于m非常大(4294434817)，所以我使用long long来存储结果。然而，在运行过程中，long long仍然显得不够。例如，我得到一个负数 (3623752876 * 3623752876) % 4294434817。

有办法解决吗？

Answer 1

所有这三个常数都在 2³¹ 和 2³² 之间。

类型unsigned long long保证能够存储至少 2⁶⁴-1 的值，这超过了乘积 3623752876 * 3623752876 .

所以只需使用 unsigned long long用于计算。 long long足够宽以容纳各个常数，但不能容纳乘积。

您还可以使用uint64_t ，定义于 <stdint.h> 。不像 unsigned long long ，它保证正好 64 位宽。由于您实际上并不需要 64 位的精确宽度(128 位算术也可以工作)， uint_least64_t或uint_fast64_t可能更合适。但是unsigned long long可以说更简单，在这种情况下它可以正常工作。 ( uint64_t 不保证存在，但在任何 C99 或更高版本的实现上几乎肯定会存在。)

对于更大的值，包括中间结果，您可能需要使用比 unsigned long long 更宽的值。 ，这可能需要某种多精度算术。 GNU GMP图书馆是一种可能性。另一种方法是使用内置支持任意宽度整数算术的语言(例如 Python)。