如何计算(A*B)%C？

Question

有人可以帮助我如何计算(A*B)%C,1<=A,B,C<=10^18在C++中,没有big-num,只是一种数学方法.

Answer 1

在我的头顶(没有经过广泛测试)

typedef unsigned long long BIG;
BIG mod_multiply( BIG A, BIG B, BIG C )
{
    BIG mod_product = 0;
    A %= C;

    while (A) {
        B %= C;
        if (A & 1) mod_product = (mod_product + B) % C;
        A >>= 1;
        B <<= 1;
    }

    return mod_product;
}

这具有复杂性O(log A)迭代.您可以%使用条件减法替换大部分内容,以获得更高的性能.

typedef unsigned long long BIG;
BIG mod_multiply( BIG A, BIG B, BIG C )
{
    BIG mod_product = 0;
    // A %= C; may or may not help performance
    B %= C;

    while (A) {
        if (A & 1) {
            mod_product += B;
            if (mod_product > C) mod_product -= C;
        }
        A >>= 1;
        B <<= 1;
        if (B > C) B -= C;
    }

    return mod_product;
}

这个版本只有一个长整数模 - 它甚至可能比大块方法更快,这取决于你的处理器如何实现整数模.

• 现场演示:https://ideone.com/1pTldb-与Yakk相同的结果.