Miller-Rabin算发快速判断素数

别人链接：1^@^1

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxm=2e5+7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
mt19937 read(time(0));
ll mul(ll a,ll b,ll p) {
    ll res(0);
    while(b) {
        if(b&1) res=(res+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return res;
}
ll qpow(ll a,ll b,ll p) {
    ll res(1);
    while(b) {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
bool MR(int n) {
    int m=n-1,t(0);
    if(n==2) return true;
    if(n<2||!(n&1)) return false;
    while(!(m&1)) {
        m>>=1;
        ++t;
    }
    for(int i=0; i<20; ++i) {
        ll a=read()%(n-1)+1,x=qpow(a,m,n),y;
        for(int j=0; j<t; ++j) {
            y=mul(x,x,n);
            if(y==1&&x!=1&&x!=n-1) return false;
            x=y;
        }
        if(x!=1) return false;
    }
    return true;
}