Miller_Rabin板子

??Miller_Rabin模板

inline LL mul(LL a, LL b, LL m) {// 计算 a*b mod m
    LL res = 0;
    while(b){
        if(b&1){
            res=(res+a)%m;
        }
        a=(a+a)%m;
        b>>=1;
    }
    return res;
}
inline LL qpow(LL a, LL b, LL m){ // 计算 a^b mod m
    LL res = 1;
    while(b){
        if(b&1){
            res=mul(res,a,m);
        }
        a=mul(a,a,m);
        b>>=1;
    }
    return res;
}
inline bool check(LL a, LL n) {
    if (n == 2 || a >= n) return 1;
    if (n == 1 || !(n & 1)) return 0;
    LL d = n - 1;
    while (!(d & 1)) d >>= 1;
    LL t = qpow(a, d, n); 
    while (d != n - 1 && t != 1 && t != n - 1) {
        t = mul(t, t, n);
        d <<= 1;
    }
    return t==n-1 || d & 1;
}

inline bool Miller_Rabin(LL n) {
    static vector<LL> t = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    if (n <= 1) return false;
    for (LL k: t){
        if(!check(k, n))return false;
    }
    return true;
}

int 2, 7, 61
long long 2, 325, 9375, 28178, 450775, 9780504, 1795265022
3e15内 2, 2570940, 880937, 610386380, 4130785767
4e13内 2, 2570940, 211991001, 3749873356

测代码准确性，hdu2138

GitHub看菊苣的板子突然想起之前的就要整的，又偷懒，直接copy了菊苣GitHub板子

Miller_Rabin板子

原文：https://www.cnblogs.com/luoyugongxi/p/14618954.html