1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include "cstdio"
#include "iostream"
#include "algorithm"
using namespace std;
typedef long long LL;
LL prime[6] = {2, 3, 5, 233, 331};
LL qmul(LL x, LL y, LL mod)   // 乘法防止溢出， 如果p * p不爆LL的话可以直接乘； O(1)乘法或者转化成二进制加法(快速加)
{
    LL ret = 0;
    while(y) {
        if(y & 1)
            ret = (ret + x) % mod;
        x = x * 2 % mod;
        y >>= 1;
    }
    return ret;
}
LL  Qpow (LL base,LL m,LL mod){
    LL ans=1;
    while(m){
        if(m&1) ans=qmul(ans,base,mod);
        base=qmul(base,base,mod);
        m>>=1;
    }
    return ans;
}
bool Miller_Rabin(long long n){
    if(n<2) return false;
    if(n==2) return true;
    if(n%2==0) return false;
    LL u=n-1;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX