如何计算(A*B)%C？ [复制]

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

从我的脑海中浮现出来（未经广泛测试）

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 https://ideone.com/1pTldb-- 与 Yakk 的结果相同。