用原始类型进行模乘法的方法

小编典典

用原始类型进行模乘法的方法

algorithm

有(853467 * 21660421200929) % 100000000000007没有没有BigInteger库的构建方法（请注意，每个数字都适合64位整数，但乘法结果不适合）？

此解决方案似乎效率低下：

int64_t mulmod(int64_t a, int64_t b, int64_t m) {
    if (b < a)
        std::swap(a, b);
    int64_t res = 0;
    for (int64_t i = 0; i < a; i++) {
        res += b;
        res %= m;
    }
    return res;
}

阅读 235

2020-07-28

共1个答案

小编典典

您应该使用俄罗斯农民乘法。它使用重复加倍来计算所有值(b*2^i)%m，如果设置了i第th位，则将它们相加a。

uint64_t mulmod(uint64_t a, uint64_t b, uint64_t m) {
    int64_t res = 0;
    while (a != 0) {
        if (a & 1) res = (res + b) % m;
        a >>= 1;
        b = (b << 1) % m;
    }
    return res;
}

它改进了您的算法，因为它需要O(log(a))时间，而不是O(a)时间。

警告：无符号，仅在m小于或等于63位时有效。

2020-07-28