zcmimi's blog
avatar
zc
2020-03-19 23:44:00
  • 本文总阅读量
查看原题

点击跳转

经过一番化简后变成了:

\sum_{i=1}^{\sqrt{2n}} \sum_{x=L}^{R} [\gcd(i,x)=1] \\ L=Max(1,i-\lfloor {n\over i}\rfloor) \\ R=Min(i-1,\lfloor {n\over i }\rfloor)

莫比乌斯反演

\sum_{i=1}^{\sqrt{2n}} \sum_{j=l}^{R} [\gcd(i,j)=1] \\ =\sum_{i=1}^{\sqrt{2n}} \sum_{j=l}^{R} \sum_{k|i,k|j} \mu(k) \\ =\sum_{i=1}^{\sqrt{2n}}\sum_{k|j,k\in[L,R]} \mu(k)

#include<bits/stdc++.h>
typedef long long ll;
const int N=1500011;
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
inline int abs(int x){return x>0?x:-x;}
ll n;
int m,mu[N],pri[N],cnt=0,head[N];
bool b[N];
struct edge{int to,nxt;}e[N<<4];
inline void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
inline ll calc(int x,int k){
    ll res=0;
    for(int i=head[x];i&&abs(e[i].to)<=k;i=e[i].nxt)
        res+=k/e[i].to;
    return res;
}
int main(){
    scanf("%lld",&n);
    m=sqrt((n<<1));
    mu[1]=1;
    for(int i=2;i<=m;++i){
        if(!b[i])pri[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&i*pri[j]<=m;++j){
            b[i*pri[j]]=1;
            if(i%pri[j])mu[i*pri[j]]=-mu[i];
            else break;
        }
    }
    cnt=0;
    for(int i=1;i<=m;++i)
        for(int j=1;i*j<=m;++j)
        if(mu[j])add(i*j,mu[j]*j);
    ll ans=0;
    for(int i=1;i<=m;++i)
        ans+=calc(i,min(i-1,n/i))-calc(i,max(1,i-(n/i))-1);
    printf("%lld\n",ans);
}
LG 4844 LJJ爱数数
comment评论
Search
search