0.引入
那年，机房里来了个新教练， 口胡鼻祖lhy
第一节课，带我们体验了暴力的神奇，
第二节课，带我们体验了随机数的玄妙，
……
那节课，便是我第一次接触到Miller Rabbin算法，
直到现在，终于搞懂了一些。
该算法（名字过长，不想打了）主要是解决快速判断一个极大的数是否是质数的问题。
我们知道，能保证正确的最快的算法，就是的复杂度，不能再小了，对于一个很大的long long，复杂度达到O(1e9)
但是该算法却能在的时间复杂度内判断，（如果用了光速乘，还可以变为）
那究竟是为什么呢？
我们先特判了小质数后，再进入下面的算法
1.费马定理
我们知道，对于一个质数p，和比它小的数a，有
所以我们可以先判断 p 是否符合费马定理，不符合就肯定不是质数。
但是符合也不一定是质数，先不说随便在小于一个合数 p 的数中选一些数可能恰好都符合费马定理，就算把1~p-1都穷举完了，也有合数是可以满足上面的式子的，那就是卡迈克尔数。
但是这一步判断至少确定了枚举到的 a 是有逆元的吧……
2.二次探测
若有
其中 p 是质数，y < p，则
这就是二次探测的原理
然后大家知道，这篇文章不是在证定理，而是在讲算法，所以注重算法过程而不是算法推导，所以笔者就直接讲过程了！
由于上面费马定理已经判断了
而若p是质数，p-1就一定是偶数了（2已经特判掉了）可以分解出很多2出来，
设
那么先算出 ，然后每次 把它平方，只要第一次碰到 a==1 的情况，就看前一次的 a 是多少，如果不是p-1那么该数就是合数，否则就继续算法过程，总会碰到 a==1 的情况，因为最后会乘到 。
3.随机数
随便选一个数 a 来做二次探测，让合数躲过的几率只有10%左右，
那么随机选10个、20个、30个数做二次探测，让合数躲过的几率就小得多了，可以小到同出现相同指纹的概率这么小，（但前提是足够随机）
所以我们就放心做十次二次探测，每次选一个1~p-1中的随机 a 跑上面的过程，把这个10算作一个log的话，复杂度也只有了。
4.例题
FZU1649 质数还是合数
一道该算法的板题
CODE
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<algorithm>
#define MAXN 65545
#define MAXM 35
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x)&(x))
//#define int LL
using namespace std;
inline LL read() {
LL f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}
while(s >= '0' && s <= '9') {x = x * 10 + (s - '0');s = getchar();}
return x * f;
}
const LL jzm = 1000000007;
int n,m,i,j,s,o,k;
LL safemul(LL a,LL b,LL zxy) {
LL res = 0;if(a < b) swap(a,b);
while(b>0) {
if(b & 1ll) (res += a) %= zxy;
(a <<= 1ll) %= zxy;
b >>= 1;
}
return res;
}
LL qkpow(LL a,LL b,LL zxy) {
LL res = 1;
while(b>0) {
if(b & 1ll) res = safemul(res,a,zxy);
a = safemul(a,a,zxy);
b >>= 1;
}
return res % zxy;
}
LL Rand() {return rand()*rand()+rand();}
bool Miller_rabbin(LL p) {
if(p == 2 || p == 3 || p == 5) return 1;
if(p <= 1) return 0;
LL nm = p-1;
nm /= lowbit(nm);
for(int id = 1;id <= 10;id ++) {
LL a = Rand() % p;
if(qkpow(a,p-1,p) != 1ll) return 0;
a = qkpow(a,nm,p);
LL pre = p-1;
while(a != 1) {
pre = a;
a = safemul(a,a,p);
}
if(pre != p-1) return 0;
}
return 1;
}
int main() {
srand(time(0));
LL N;
while(scanf("%lld",&N) == 1) {
printf(Miller_rabbin(N) ? "It is a prime number.\n":"It is not a prime number.\n");
}
return 0;
}
