rt 本蒟蒻抄的模板QwQ 但不理解为什么O(klogn^3)会过不了呢 不知道这是不是我的错觉 总感觉这个比普通筛系数+复杂度都低 但时间就是会超很多很多 (plus Q:那这种米勒筛应该什么时候用呢?)

#include<bits/stdc++.h>
using namespace std;

long long qmul(long long a,long long b,long long mod)//快速乘
{
    long long c=(long long)a/mod*b;
    long long res=(unsigned long long)a*b-(unsigned long long)c*mod;
    return (res+mod)%mod;
}
long long qpow(long long a,long long n,long long mod)//快速幂
{
    long long res=1;
    while(n)
    {
        if(n&1) res=qmul(res,a,mod);
        a=qmul(a,a,mod);
        n>>=1;
    }
    return res;
}
bool MRtest(long long n)//Miller Rabin Test
{
    if(n<3||n%2==0) return n==2;
    long long u=n-1,t=0;
    while(u%2==0) u/=2,++t;
    long long ud[]={2,325,9375,28178,450775,9780504,1795265022};
    for(long long a:ud)
    {
        long long v=qpow(a,u,n);
        if(v==1||v==n-1||v==0) continue;
        for(int j=1;j<=t;j++)
        {
            v=qmul(v,v,n);
            if(v==n-1&&j!=t){v=1;break;}
            if(v==1) return 0;
        }
        if(v!=1) return 0;
    }
    return 1;
}

int main()
{
	int l,r;
	cin>>l>>r;
	int count=0;
	for (int i=l;i<=r;i++)
	{
		if (MRtest(i)==1) count++;
	}
	cout<<count;
}
[评测结果](https://www.luogu.com.cn/record/140019472)