Miller-Rabin

Miller-Rabin

例题：loj 143. 质数判定

#include <cstdio>

typedef long long ll;
typedef unsigned long long ull;

int pri[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};

ll Mul(ll a, ll b, ll M) {
    return (((ull)a * b - (ull)((long double)a * b / M) * M) + M) % M;
}

ll Pow(ll a, ll k, ll M, ll ans = 1) {
    for (; k; k >>= 1, a = Mul(a, a, M))
        if (k & 1) ans = Mul(ans, a, M);
    return ans;
}

bool Judge(ll x) {
    if (x == 1) return 0;
    for (int i = 0; i < 9; ++i) {
        if (x == pri[i]) return 1;
        ll k = x - 1, p = Pow(pri[i], k, x);
        if (p != 1) return 0;
        while (p == 1 && k % 2 == 0) {
            p = Pow(pri[i], k >>= 1, x);
            if (p != 1 && p != x - 1) return 0;
        }
    }
    return 1;
}

int main() {
    ll x;
    while (scanf("%lld", &x) == 1) puts(Judge(x) ? "Y" : "N");
    return 0;
}