如何在ACM竞赛中高效地判断一个大数是否为素数？请详细介绍米勒-拉宾伪素数测试的原理及其实现。

在ACM编程竞赛中，面对大数素数判断的问题时，传统的判断方法因其高昂的时间复杂度并不适用。此时，米勒-拉宾伪素数测试（Miller-Rabin primality test）提供了一种有效的概率性判断方案，该算法基于费马小定理，并且具有相对较高的效率和准确性。

参考资源链接：[ACM竞赛中判断素数的方法：从朴素到优化](https://wenku.csdn.net/doc/8bg9wh9cgr?spm=1055.2569.3001.10343)

米勒-拉宾测试是一种概率算法，用于判断一个大整数n是否为素数。其基本原理是：对于一个奇数n > 2，如果n是素数，那么对于任意的整数a（1 < a < n-1），n和a满足以下两个条件之一：
1. a^(n-1) ≡ 1 (mod n)
2. 存在某个整数r（0 ≤ r < s），使得a^(2^r * (n-1)) ≡ -1 (mod n)

其中，n-1可以写成2^s * d的形式，d为奇数。通过多次选择不同的a值进行测试，可以以非常高的概率断定n的素性。在实际实现中，通常会选取多个a（例如5个）来测试，以降低误判的概率。

以下是一个简化的米勒-拉宾测试的伪代码实现：

bool MillerRabin(int n, int a) {
    if (n == a) return true;
    int d = n - 1;
    while (d % 2 == 0) d /= 2; // 找到n-1 = 2^s * d的形式
    if (pow(a, d, n) == 1) return true; // a^d ≡ 1 (mod n)
    for (int r = 0; r < s; r++) { // 检查是否存在r使得a^(2^r * d) ≡ -1 (mod n)
        if (pow(a, (d << r), n) == n - 1) return true;
    }
    return false; // 以上条件均不满足，则n可能是合数
}

在上述代码中，`pow(a, d, n)` 表示计算a^d对n取模的结果，使用快速幂算法可以进一步优化性能。

如果你希望深入掌握从朴素判断到米勒-拉宾测试这一系列素数判断方法，推荐阅读《ACM竞赛中判断素数的方法：从朴素到优化》。这本书详细介绍了ACM竞赛中判断素数的多种方法，从基础的朴素判断到更高级的概率性测试，内容全面且实用，非常适合想要提高算法竞赛水平的读者。

参考资源链接：[ACM竞赛中判断素数的方法：从朴素到优化](https://wenku.csdn.net/doc/8bg9wh9cgr?spm=1055.2569.3001.10343)