LOJ143. 质数判定 题解 Miller–Rabin 素性测试

题目链接：https://loj.ac/p/143

解题思路：完全来自 oi.wiki

时间复杂度：\(O(k \log^3 n)\)。

---

Miller–Rabin 素性测试 的结论

对于一个奇数 \(n\)，将 \(n - 1\) 表示为

\[n - 1 = 2^s \cdot d \]

其中，\(d\) 是一个奇数。

则：

• 如果存在一个 \(r(0 \le r \le s-1)\) 满足 \(a^{2^r d} \equiv 1 (\text{ mod } n)\)，则 \(n\) 是素数；
• 如果 \(a^d \equiv 1 (\text{ mod } n)\)，则 \(n\) 是素数；
• 如果存在一个 \(r(1 \le r \le s-1)\) 满足 \(a^{2^r d} \equiv 1 (\text{ mod } n)\)，则 \(n\) 不是素数。

---

示例程序：

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

ll fpow(ll a, ll b, ll m) {
    ll res = 1;
    for (ll t = a % m; b; b >>= 1, t = (__int128)t * t % m)
        if (b & 1ll)
            res = (__int128) res * t % m;
    return res;
}

bool miller_rabin(ll n, ll a) {
    ll d = n - 1, s = 0;
    while (d % 2 == 0) d >>= 1, s++;
    ll x = fpow(a, d, n);
    if (x == 1 || x == n-1)
        return true;
    for (int i = 1; i < s; i++) {
        x = (__int128) x * x % n;
        if (x == n-1)
            return true;
        if (x == 1)
            return false;
    }
    return false;
}

bool prime(ll n) {
    if (n == 2) return true;
    if (n < 2 || n % 2 == 0) return false;
    for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23}) {
        if (n == a)
            return true;
        if (!miller_rabin(n, a))
            return false;
    }
    return true;
}

int main() {
    ll n;
    while (~scanf("%lld", &n)) {
        puts(prime(n) ? "Y" : "N");
    }
    return 0;
}