Miller-Rabin Primality Test

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

ll mulmod(ll a, ll b, ll m) { return (__int128)a * b % m; }

ll powmod(ll a, ll d, ll m) {
    ll res = 1; a %= m;
    while (d > 0) {
        if (d & 1) res = mulmod(res, a, m);
        a = mulmod(a, a, m);
        d >>= 1;
    }
    return res;
}

bool millerRabin(ll n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0) return false;
    ll d = n - 1; int s = 0;
    while (d % 2 == 0) { d /= 2; s++; }
    for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (a >= n) continue;
        ll x = powmod(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool comp = true;
        for (int r = 1; r < s; r++) {
            x = mulmod(x, x, n);
            if (x == n - 1) { comp = false; break; }
        }
        if (comp) return false;
    }
    return true;
}