Miller-Rabin 的推导本质上是把费马小定理和二次探测定理串联起来，形成一个可高效验证的判定链。

费马小定理告诉我们：若 $p$ 是素数，$\gcd(a,p)=1$，则

$$a^{p-1} \equiv 1 \pmod p$$

我们想用它的逆否命题来判合数：若 $a^{n-1} \not\equiv 1 \pmod n$，则 $n$ 是合数。

问题：存在合数（Carmichael 数）使得 $a^{n-1} \equiv 1 \pmod n$ 对某些 $a$ 成立。仅靠费马小定理会漏判。

若 $p$ 是奇素数，且 $x^2 \equiv 1 \pmod p$，则

$$x \equiv 1 \pmod p \quad \text{或} \quad x \equiv -1 \pmod p$$

逆否命题：若在模 $n$ 下算出 $x^2 \equiv 1$，但 $x \not\equiv \pm 1 \pmod n$，则 $n$ 一定是合数。

为了把二次探测嵌入费马测试，我们将 $n-1$ 分解为：

$$n - 1 = 2^s \cdot d \quad (d \text{ 为奇数})$$

这样 $a^{n-1}$ 可以写成一个逐步平方的链：

$$a^{n-1} = a^{2^s \cdot d} = \underbrace{(\cdots((a^d)^2)^2\cdots)^2}_{s \text{ 次平方}}$$

定义序列：

$$t_0 = a^d, \quad t_1 = t_0^2, \quad t_2 = t_1^2, \quad \dots, \quad t_s = t_{s-1}^2 = a^{n-1}$$

• 若满足 $t_0 = a^d \equiv \pm 1 (\bmod \ n)$。此时费马/二次探测直接判定。

• 若满足 $t_0 \not\equiv \pm 1$。但我们知道最终 $t_s = a^{n-1} \equiv 1 \pmod n$（费马小定理）。既然序列从"非 $\pm 1$"变到了"$1$"，那么在某个位置必然发生了 从 $n-1$ 到 $1$ 的跳变（因为 $n-1$ 是 $1$ 在模素数下唯一的另一个平方根）。

  即：存在某个 $j \in [1, s]$，使得

  $$t_{j-1} \equiv n-1 \pmod n \quad \text{且} \quad t_j = t_{j-1}^2 \equiv 1 \pmod n$$

合并结论：若 $n$ 是素数，则对任意基底 $a$，序列 $\{t_i\}$ 中要么 $t_0 \equiv \pm 1$，要么存在某个 $t_j \equiv n-1$（$0 \le j < s$）。

对上述结论取逆否命题，就得到了 Miller-Rabin 的合数判定条件：

若对某个基底 $a$，序列 $\{t_i\}$ 满足：

1. $t_0 \not\equiv 1$ 且 $t_0 \not\equiv n-1$；
2. 对所有 $j \in [1, s]$，$t_j \not\equiv n-1$；

则 $n$ 一定是合数。

若所有选定基底都不触发上述合数条件，则 $n$ 为素数（在确定性基底集下可严格证明）。

算法逻辑:

对每个选定的基底 $p$ ，令 $t = p^d \bmod n$ ，d 为 $n−1$ 去掉所有因子 $2$ 后剩下的奇数部分：

1. 若 $t=1$ 或 $t=n-1$，本轮通过。
2. 否则，将 $t$ 反复平方最多 $s$ 次。若某次平方后得到 $n-1$，本轮通过。
3. 若始终没得到 $n-1$，则 $n$ 是合数。
4. 若所有选定基底都通过，则 $n$ 是素数。

代码中选用了前 15 个素数 {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47} 作为测试基底。前 15 个素数的基底已被数学证明：在 __int128 范围内该测试是绝对安全的。

算法时间复杂度为 $O(Klog^2N)$ ，其中 $K$ 为基底。

代码

#include<bits/stdc++.h>
#define int __int128 // 扩展精度，支持约1.7×10^38范围
using namespace std;

// 确定性测试基底，覆盖__int128范围
const int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};

template<typename T>inline void qr(T &x){
	int f=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	x*=f;
}

template<typename T>inline void qw(T x){
	if(x<0) putchar('-'),x=-x;
	if(x/10) qw(x/10);
	putchar(x%10+'0');
}

inline int qpow(int a,int b,int m){
    int res=1; a%=m;
    for(;b;b>>=1,a=(a*a)%m)
        if(b&1) res=(res*a)%m;
    return res;
}

// Miller-Rabin确定性素性测试
inline bool Is_prime(int x){
	if(x<2) return false;
	// 小数直接查表
	if(x<=37){
		for(int p:prime) if(x==p) return true;
		return false;
	}
	// 分解x-1 = 2^s * d
	int d=x-1,s=0;
	while(!(d&1)) d>>=1,s++;
	// 逐个基底测试
	for(int y:prime){
		if(y>=x) break;
		int t=qpow(y,d,x);
		// 首项为1或x-1，本轮通过
		if(t==1||t==x-1) continue;
		// 二次探测：反复平方检查是否出现x-1
		bool flg=false;
		for(int j=1;j<=s;j++){
			t=t*t%x;
			if(t==x-1){ flg=true; break; }
		}
		// 未通过二次探测，必为合数
		if(!flg) return false;
	}
	return true; // 所有基底通过，确定为素数
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T; qr(T);
	while(T--){
		int n; qr(n);
		puts(Is_prime(n)?"Yes":"No");
	}
}

#include<bits/stdc++.h>
#include "prime.hpp"
using namespace std;
int main()
{
	int q;cin>>q;
	while(q--)
	{
		long long n;cin>>n;
		if(is_prime(n))puts("Yes");
		else puts("No");
	}
	return 0;
}