当分母超出 unsigned long long int 范围时如何使用模数？

Question

给定 1 ≤ N ≤ 10¹⁸ 和 1 ≤ K ≤ 10¹⁸，我该如何操作 N % K²?当 K 接近值 10²（分母）超出 unsigned long long int 的范围时 ¹⁸，因此我无法存储该值K2.

Answer 1

你真的不需要 bigint 库，因为

• 如果 K > 10⁹ 那么 K² > 10¹⁸ > N, 因此N % K² = N 不用计算K²
• if K ⩽ 10⁹ 那么你可以使用正常的 uint64_t 计算 N % (K*K) 而不会溢出

FWIW 大多数现代编译器在 64 位模式下也有 128 位类型。 GCC、Clang 和 ICC 称之为 __int128

见Is there a 128 bit integer in gcc?

Answer 2

那么如果 K² 大于 N 那么 N % K² 等于 N.

示例：

253 % 17² = 253 % 289 = 253

假设 64 位 unsigned long long，可以平方而不会溢出的最大值是 2³² - 1 等于 0xFFFFFFFF（或 4'294' 967'295).

因此您可以简单地使用以下代码：

unsigned long long compute(unsigned long long n, unsigned long long k)
{
    if (k > 0xFFFFFFFF)
    {
        // k² is bigger than n (require more than 64 bits), so the modulo is n
        return n;
    }

     return n % (k * k);
}