【模板】质数判定（Miller-Rabin）题解

题目大意

输入若干行，每行一个整数（），判断是否为质数。
如果是质数输出 Y，否则输出 N。

算法分析

朴素判断法

对于每个数，试除内的所有整数，时间复杂度。
当高达时，，无法在题目要求的 500ms 内完成。

Miller–Rabin 素性测试

Miller–Rabin 是一种基于概率的素性测试，通过对 费马小定理 和 二次探测定理 的多次检验，可以以极高的准确率判定一个数是否为质数。
对于 64 位整数，选取特定的 确定性基 后，可以在的时间复杂度内得到 100% 正确的结果。

理论基础

费马小定理：若是质数，且与互质，则。
反过来，若存在使得，则一定是合数。
二次探测定理：若是奇质数，的解为。
即若但，则为合数。

算法步骤

对于待测奇数：

将写成的形式，其中为奇数。
选择一组基（对于，取确定性基即可）。
对每个：
- 计算。
- 如果或，则通过本轮测试。
- 否则，重复平方共次：
  - 若某次得到，则通过测试。
  - 若某次得到且上一次，则为合数。
- 若最终不满足任何条件，返回合数。
所有基都通过，则为质数。

确定性基的选择

对于，选取以下 7 个基即可保证 100% 正确：

（实际上前 3 个基已经可以判定的情况，全部 7 个基覆盖整个 64 位范围。）

快速乘（避免溢出）

在计算时，直接相乘可能溢出 64 位。可以使用 快速乘（基于加法倍增）或 __int128（如果编译器支持）。

方法一：__int128（GCC 支持）

using ll = long long;
using i128 = __int128_t;
inline ll mul(ll a, ll b, ll m) {
    return (ll)((i128)a * b % m);
}

方法二：手动快速乘（适用于不支持 __int128 的环境）

ll mul(ll a, ll b, ll m) {
    ll res = 0;
    a %= m;
    while (b) {
        if (b & 1) res = (res + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return res;
}

时间复杂度

每个数进行次测试（为基的数量，此处）。
每次测试需要次快速幂（包含快速乘），总复杂度。
对于，单次判定可在微秒级完成，完全满足题目要求。

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;

// 快速乘（使用 __int128）
ll mul(ll a, ll b, ll m) {
    return (ll)((i128)a * b % m);
}

// 快速幂
ll qpow(ll a, ll b, ll m) {
    ll res = 1;
    a %= m;
    while (b) {
        if (b & 1) res = mul(res, a, m);
        a = mul(a, a, m);
        b >>= 1;
    }
    return res;
}

// Miller–Rabin 确定性测试
bool isPrime(ll n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;

    // 将 n-1 写成 d * 2^s
    ll d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        ++s;
    }

    // 确定性基（覆盖 64 位）
    static const ll bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};

    for (ll a : bases) {
        if (a % n == 0) continue; // 跳过 a 是 n 的倍数的情况
        ll x = qpow(a, d, n);
        if (x == 1 || x == n - 1) continue;

        bool composite = true;
        for (int r = 1; r < s; ++r) {
            x = mul(x, x, n);
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll x;
    while (cin >> x) {
        cout << (isPrime(x) ? "Y" : "N") << '\n';
    }
    return 0;
}

注意事项

特判小数字：的情况需要单独处理，否则算法中的会产生负数或除以零。
偶数提前返回：除 2 以外的偶数直接判合数，可以加速。
基的选择：上述 7 个基足以正确判定所有 64 位整数。如果需要更小的常数，可以针对只使用 {2, 7, 61}。
快速乘的必要性：在计算时，两个级别的数相乘会达到，直接使用 64 位整数会溢出，必须采用 __int128 或手动模拟。
输入处理：题目没有明确给出数据组数，需要读入直到 EOF。

总结

Miller–Rabin 素性测试是解决大范围质数判定问题的标准模板，通过选择确定性基可以在不牺牲正确性的前提下获得极高的运行效率。掌握该算法对于参加算法竞赛和解决相关问题都有很大帮助。