『算法-ACM 竞赛-数学-数论』Miller_Rabin 判断一个大数是不是素数（随机算法）

前提知识
1，费马定理：$a^{p-1}=1(mod\ p)$😀 点我
2，二次探测定理：$x^{2}\equiv 1(mod\ p)\Rightarrow x=1||p-1$😀 点我
但我们注意到，费马定理其逆定理不能直接用来判断素数，必须要枚举很多数，一般情况下我们可以枚举到 1000 左右，就可以把 long long 范围内的大部分数给判断完成。

也有例外，即存在一种极端反例卡迈克尔数（一种合数），对于任何卡迈克尔叔，费马定理都成立。虽然这种极少，在 1e8 范围内的整数中，只有 255 个卡迈克尔数。但不管怎么说还是会被出题人卡死，或者被人 hack，虽然这种算法的出错率为 4^-k（k 为测试数据的个数）。

而为了防止这种情况出现，有一种东西，叫二次探测定理：
如果 p 是奇素数，则 x≡1(mod p)的解为 x=1 或 x=p-1(mod p)，这个由模运算的性质易得。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int times = 10;
ll fast_mod(ll a,ll b,ll mod)//计算2^q的过程
{
    ll res = 0;
    while(b){
        if(b & 1) res = res + a;
        a <<= 1;
        if(a >= mod) a -= mod;
        if(res >= mod) res -= mod;
        b >>= 1;
    }
    return res;
}
ll fast_pow_mod(ll a,ll b,ll mod)//快速幂算出a^m
{
    ll res = 1;
    while(b){
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
bool check(ll a,ll m,ll p,ll n)//对于每次随机的a进行测试
{
    ll temp = fast_pow_mod(a,m,n),ret = temp;
    for(int i = 0;i < p;++i){
        ret = fast_mod(temp,temp,n);
        if(ret == 1 && temp != n - 1 && temp != 1) return true;
        temp = ret;
    }
    return ret != 1;
}
bool Miller_Pabin(ll n)//Miller测试的主体结构
{
    if(n < 2) return false;
    if(n == 2) return true;
    if(n & 1 == 0) return false;//对于偶数的优化
    ll p = 0,x = n - 1;//p为Miller测试的q，x为Miller测试的m
    while(x & 1 == 0){
        x >>= 1;
        p++;
    }
    srand(time(NULL));
    for(int i = 0;i < times;++i){
        ll o = rand() % (n - 1) + 1;//o就是Miller测试的底数a
        if(check(o,x,p,n)) return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--){
        long long n;
        cin >> n;
        cout << (Miller_Pabin(n) ? "Prime" : "Not a Prime") << endl;
    }
    return 0;
}