在做这道题之前，我们首先来尝试签到题。

签到题

我们定义一个函数：\(qiandao(x)\) 为小于等于 x 的数中与 x 不互质的数的个数。要求 \(\sum\limits _{i=l}^r qiandao(i)\)

容易发现 \(qiandao(x)\) 只需求 \(\phi(x)\),不互质的个数就是另外一半。

那么问题转化为了如何筛出区间 \(\phi\) 的值。考虑到值域最大只有 \(1e12\)。并且区间长度小于一百万，所以可以尝试筛根号以内素数求解。

我们知道欧拉函数计算公式为 \(\prod_{d \mid p}\frac{d-1}{d}\) 其中 d 是 p 的质因数。

于是我们可以通过筛去根号以内每个质数计算大整数区间的欧拉值，而剩下筛不掉的一定是大于根号的质数，这个直接根据上式乘上就行了。

复杂度与自然对数有关，和调和级数类似。

小清新数学题

求解 \(\sum\limits_{i=l}^r\mu(i)\)

现在我们掌握了区间筛积性函数的方法，但是，这道题的数据范围到了 \(1e18\)。我们不可能晒出十亿以内的质数。

那么怎么办呢？

注意到本题求得是莫比乌斯函数，根据莫比乌斯函数的定义，函数值只与质因子的个数有关，我们不需要求出具体的质数是谁，只需要知道有几个就行。

于是我们仍然可以用一百万以内的质数去筛。

剩下的情况分三种：

\(res=q\times p\)
\(res=q\)
\(res=q^2\)

首先对于第一种情况，莫比乌斯函数值并不会改变。

第二种情况，取反即可。

第三种情况，直接就是 0。

第三种情况好判断，只需判断是否满足 \(\sqrt{i}^2==i\) 。

对于一二种情况，实质实在判断 res 是否是素数，于是引出了我们的另一个问题。如何判断一个数是否是素数？

Miller_Rabin 算法

百度百科：

Miller-Rabin算法是目前主流的基于概率的素数测试算法，在构建密码安全体系中占有重要的地位。通过比较各种素数测试算法和对Miller-Rabin算法进行的仔细研究，证明在计算机中构建密码安全体系时， Miller-Rabin算法是完成素数测试的最佳选择。通过对Miller-Rabin 算法底层运算的优化，可以取得较以往实现更好的性能。[1] 随着信息技术的发展、网络的普及和电子商务的开展，信息安全逐步显示出了其重要性。信息的泄密、伪造、篡改等问题会给信息的合法拥有者带来重大的损失。在计算机中构建密码安全体系可以提供4种最基本的保护信息安全的服务：保密性、数据完整性、鉴别、抗抵赖性，从而可以很大程度上保护用户的数据安全。在密码安全体系中，公开密钥算法在密钥交换、密钥管理、身份认证等问题的处理上极其有效，因此在整个体系中占有重要的地位。目前的公开密钥算法大部分基于大整数分解、有限域上的离散对数问题和椭圆曲线上的离散对数问题，这些数学难题的构建大部分都需要生成一种超大的素数，尤其在经典的RSA算法中，生成的素数的质量对系统的安全性有很大的影响。目前大素数的生成，尤其是随机大素数的生成主要是使用素数测试算法，本文主要针对目前主流的Miller-Rabin 算法进行全面系统的分析和研究，并对其实现进行了优化

这个看个热闹就完了，其实这个东西我们只用来判断一个数是否是素数。以下内容说到的 p 默认为质数。

Miller Rabin基于费马小定理：

\[a^{p-1}\equiv 1\pmod{p}
\]

证明：

对于数 \(a,2a,3a,.....(p-1)a\) 没有 \(p\) 的倍数。
对于这一列数在模 \(p\) 意义下两两不同余。
这串数在模 \(p\) 意义下的余数构成 \(p-1\) 的一个排列。

于是有：

\[a\times 2a\times 3a\times (p-1)a\equiv (p-1)!\pmod{p}
\]

化简左边：

\[a^{p-1}\times (p-1)!\equiv (p-1)!\pmod{p}
\]

由威尔逊定理：

\[(p-1)!\equiv1\pmod{p}
\]

消去 \((p-1)!\) 得证。

费马小定理成立，那么如果费马小定理的逆命题成立我们不就可以判断质数了吗？

可惜，很长时间里人们确实是这样认为的，直到强伪素数被人们发现，例如341。

再来介绍二次探测定理：

如果满足\(x^2\equiv1\pmod{p}\) 那么 x 的取值只有 1 或者 p-1。

证明：

转换上式：

\[p\mid x^2-1
\]

\[p\mid (x-1)(x+1)
\]

由唯一分解定理得到\(p \mid x+1\) 或 \(p\mid x-1\)

所以 \(x\equiv1 or -1\pmod{p}\)。

如果 x 不满足上式则 p 一定是合数。

所谓 Miller Rabin 就是上面的结合。说白了就是多取几个数多试几次，这样出错的概率极低。

签到题code

#include<bits/stdc++.h>

#define int long long

#define mod 666623333

using namespace std;

int su[10000001],cnt,ans[1000011],len,lst=0,l,r,shu[1000011];

bool bo[10000001];

inline void pre()

{   for(int i=2;i<=1000000;++i)

    {   if(!bo[i])su[++cnt]=i;

        for(int j=1;j<=cnt and i*su[j]<=1000000;++j)

        {   bo[su[j]*i]=1;

            if(i%su[j]==0)break;

        }

    }

}

signed main()

{   pre();scanf("%lld%lld",&l,&r);len=r-l+1;

    for(int i=1;i<=len;++i)ans[i]=shu[i]=i+l-1;

    for(int i=1;i<=cnt;++i)

    {   int base=l/su[i];

        for(int j=base;;++j)

        {   if(j*su[i]>=l and j*su[i]<=r)

            {   ans[j*su[i]-l+1]=(ans[j*su[i]-l+1]/su[i]*(su[i]-1));

                while(shu[j*su[i]-l+1]%su[i]==0)shu[j*su[i]-l+1]/=su[i];

            }

            else if(j*su[i]>r)break;

        }

    }

    for(int i=1;i<=len;++i)

    {   if(shu[i]!=1)ans[i]=ans[i]/shu[i]*(shu[i]-1);

        lst=(lst+(l+i-1-ans[i]))%mod;

    }

    printf("%lld\n",lst);

}

小清新数学题code

#include<bits/stdc++.h>

#define int long long

#define N 1000500

#define mfb __int128

using namespace std;

int su[N],cnt,tot,u[N],shu[N];

bool bo[N];long long l,r,ans;

inline int qpow(mfb a,mfb b){int mod=b+1,base=1;a%=mod;while(b){if(b&1)base=base*a%mod;a=a*a%mod;b>>=1;}return base;}

inline bool miller(int x)

{return (qpow(2,x-1)==1 );}

signed main()

{   scanf("%lld%lld",&l,&r);u[1]=1;

    int lim=1e6;

    for(int i=2;i<=lim;++i)

    {   if(!bo[i])su[++cnt]=i,u[i]=-1;

        for(int j=1;j<=cnt and i*su[j]<=lim;++j)

        {   bo[i*su[j]]=1;u[i*su[j]]=-u[i];

            if(i%su[j]==0){u[i*su[j]]=0;break;}

        }

    }

    for(int i=l;i<=r;++i)u[i-l+1]=1,shu[i-l+1]=i;

    for(int i=1;i<=cnt;++i)

    {   int be=l/su[i]+(l%su[i]!=0);

        for(int j=be;j*su[i]<=r;++j)

        {   int id=j*su[i]-l+1;

            int cnt=0;

            while(shu[id]%su[i]==0)shu[id]/=su[i],++cnt,u[id]*=-1;

            if(cnt>=2)u[id]=0;

        }

    }

    for(int i=l;i<=r;++i)if(shu[i-l+1]!=1)

    {   if((long long )sqrt(shu[i-l+1])*sqrt(shu[i-l+1])==shu[i-l+1]){u[i-l+1]=0;continue;}

        if(miller(shu[i-l+1]))u[i-l+1]*=-1;

    }

    for(int i=l;i<=r;++i)ans+=u[i-l+1];printf("%lld\n",ans);

}

由于数据比较水，我又比较懒，上面只用了 femart。

Miller Rabin

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=100000+5;

int a[3]={2,7,61};

ll qm(ll x,ll y,ll mod){

    ll ret=1;

    while(y){

        if(y&1) (ret*=x)%=mod;

        (x*=x)%=mod;

        y>>=1;

    }

    return ret;

}

bool che(ll a,ll x){

    int s=0;

    ll t;

    ll lp=x-1;

    while(!(lp&1)){

        s++;

        lp>>=1;

    }

    t=qm(a,lp,x);

    if(t==1||t==x-1) return true;

    if(s==0) return false;

    ll las=t;

    for(int i=0;i<s;i++){

        las=t;

        (t*=t)%=x;

        if(t==1&&(las!=1&&las!=x-1)) return 0;

    }

    if(t!=1) return 0;

    return 1;

}

int n,m;

bool M_R(ll n){

    if(n==2||n==7||n==61) return true;

    if(n<2||n%2==0||n%7==0||n%61==0) return false;

    for(int i=0;i<3;i++){

        ll b=a[i];

        if(b!=n){

            if(!che(b,n)) return false;

        }

    }

    return true;

}

int main(){

    scanf("%d%d",&n,&m);

    ll x;

    for(int i=1;i<=m;i++){

        scanf("%lld",&x);

        if(x==2||x==3||x==5||x==7||x==11||x==13){

            puts("Yes");continue;

        }

        if(x%2==0||x%3==0||x%5==0||x%7==0||x%11==0||x%13==0){

            puts("No");continue;

        }

        if(M_R(x)) puts("Yes");

        else puts("No");

    }

    return 0;

}

Miller Rabin的板子为转载，上面过的是线性筛。

巴特西

Miller Rabin 详解 && 小清新数学题题解

签到题

小清新数学题

Miller_Rabin 算法

最新文章

热门文章