题解 P3653 【小清新数学题】

· · 题解

这题好毒瘤啊...果然是zzq...

首先要去切了这道题来学会区间筛积性函数

然后你发现这题r\leq 10^{18}....处理\sqrt{r}个素数是行不通的.

但是我们注意一点，\mu函数可以认为是只和素数的个数有关的，所以我们只拿10^6个数去筛.假设i已经除去了所有1e6以下的质因子，那么i只有三种情况:

\begin{cases}i=pq\\i=p\\i=p^2\end{cases}(p,q\in prime,p\neq q)

对于第一种情况，多了两个质因子，\mu不变；对于第二种情况\mu取负；对于第三种情况\mu=0.

如何去判断呢?i=p^2只需要判断\left\lfloor\sqrt{i}\right\rfloor^2=i；i=p需要使用Miller-Rabin素性测试；剩下的就是i=pq的情况了.

首先龟速乘根本跑不动(快速幂+龟速乘是两个$\log$的)，所以 ```cpp long long mul(long long a,long long b,long long m) { return (a*b-(long long)((long double)a/m*b)*m+m)%m; } ``` 原理baidu吧QAQ 这里因为数据水而使用了简化版的$Miller-Rabin$(只测$2$和$3$，不二次探测) 注释中有正常的$Miller-Rabin 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
long long fac[2000000],l,r;
int mu[2000000],prime[2000000],p[2000005],cnt;
long long sqr(long long x){return x*x;}
void make(int n)//打表1e6的素数
{
    p[0]=p[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!p[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
        {
            p[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
long long mul(long long a,long long b,long long m)
{
    return (a*b-(long long)((long double)a/m*b)*m+m)%m;
}
long long qpower(long long a,long long b,long long m)
{
    long long ans=1;
    for(;b;b>>=1,a=mul(a,a,m))if(b&1)ans=mul(ans,a,m);
    return ans;
}
/*
bool Miller_Rabin(long long x,long long p)//真的MillerRabin，底下要选取12个素数 
{
    long long pd=qpower(p,x-1,x),s=x^1;
    while(pd==1&&!(s&1))s>>=1,pd=qpower(p,s,x);
    return pd==1||pd==(x^1);
}
*/
bool Miller_Rabin(long long x,long long p){return qpower(p,x-1,x)==1;}
bool judge(long long n)
{
    for(int i=1;i<=2;i++)if(!Miller_Rabin(n,prime[i]))return 0;
    return 1;
}
int main()
{
    scanf("%lld%lld",&l,&r);
    for(long long i=l;i<=r;i++)fac[i-l]=i,mu[i-l]=1;
    make(1000000);
    for(int i=1;i<=cnt&&prime[i]<=r;i++)
    {
        int t=prime[i];
        for(long long j=((l-1)/t+1)*t;j<=r;j+=t)
        {
            int k=0;
            while(fac[j-l]%t==0)++k,fac[j-l]/=t;
            if(k>1)mu[j-l]=0;else mu[j-l]=-mu[j-l];//区间筛
        }
    }
    long long ans=0;
    for(long long i=l;i<=r;i++)
    {   
        if(fac[i-l]!=1)
        {
            long long t=fac[i-l];
            if(sqr((long long)sqrt(t))==t)mu[i-l]=0;
            else if(judge(t))mu[i-l]=-mu[i-l];//多一个质因子
        }
        ans+=mu[i-l];
    }
    cout<<ans<<endl;
}

同理大概也可以筛\sigma...毒瘤...