2019.5.25 Noip模拟测试2 T1题解

本是古典何须时尚 2021-12-23 23:57 249阅读 0赞

![1596060-20190525150846294-1346967829.png][]

![1596060-20190525150909316-551704796.png][]

这道题数据范围较大，显然一般的素数筛法是不行的。那么如果要筛大质数，肯定要用到随机算法Miller\_Rabin，结合费马小定理a^(p-1)≡1(mod p)

但网上的Miller\_Rabin都非常繁琐，在豪哥的指导下，用他简单易懂的Miller\_Rabin算法解决该题，orz。

不过感觉这个算法真的挺玄乎的，遇上一些奇怪的数据就真没法了。

#include<bits/stdc++.h>
    #define LL long long
    using namespace std;
    const int maxn=1e6+7;
    int l,r,ans;
    int Test[]={
        2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
    int Times=13;
    long long ksm(long long x,long long n)
    {
        long long base=1;
        long long mod=n+1;
        while(n)
        {
            if(n&1) base=base*x%mod;
            n>>=1,x=(x*x)%mod;
        }
        return base%mod;
    }
    bool miller(int n)//简单易懂的Miller_Rabin
    {
        if(n<=50)
        {
            for(int i=0;i<=Times;i++)
            {
                if(n<=Test[i])    break;
                if(n%Test[i]==0)    return false;
            }
            return true;
        }
        for(int i=0;i<=Times;i++)
        {
            long long k=ksm(Test[i],n-1);//费马小定理判断
            if(k!=1) return false;
        }
        return true;
    }
    int main()
    {
        //freopen("pcount.in","r",stdin);
        //freopen("pcount.out","w",stdout);
        scanf("%d%d",&l,&r);
        l=max(2,l);
        for(int i=l;i<=r;i++)
        {
            ans+=miller(i);
        }
        printf("%d",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/10922518.html

[1596060-20190525150846294-1346967829.png]: /images/20211223/e2163f31da8045ea9876a11d55b10c22.png
[1596060-20190525150909316-551704796.png]: /images/20211223/01673b4b7b4b49a9b19048d03537f16c.png