题目描述

珈百璃刚刚学习了杜教筛，想做一道简单题练练手。给出N，求：

$\sum_{i=1}^{N}i\mu(i)$,答案对$1e9+7$ 取模

对于100%的数据，$N\leq 1e10$。

题解

利用上午讲的可以得到

$h(n)=\sum_{d|n}d\mu(d)g(\frac{n}{d})$

当$g(x)=x$时

$h(n)=\sum_{d|n}n\mu(d)$

$h(n)=n\sum_{d|n}\mu(d)$

$h(n)=n[n=1]$

再直接套模板就好了$S(n)=\frac{\sum_{i=1}^{n}h(i) - \sum_{i=2}^{n}    g(i) S(\left \lfloor \frac{n}{i} \right \rfloor) }{g(1)}$

 

#include
      
       using namespace std;#define ll long longconst int mod=1000000007;const ll inv=500000004;const int maxn=6000000;ll n;ll cnt,prime[maxn+6],mu[maxn+6],s[maxn+6];bool not_prime[maxn+6];//h=f*g//f(x)=x*mu(x)//g(x)=x//h(x)=n*[n==1]void init(){    s[1]=mu[1]=1;    for(int i=2;i<=maxn;i++){        if(!not_prime[i]){            prime[++cnt]=i;            mu[i]=-1;        }        s[i]=((s[i-1]+i*mu[i])%mod+mod)%mod;        for(int j=1;prime[j]*i<=maxn;j++){            not_prime[i*prime[j]]=true;            if(i%prime[j]) mu[i*prime[j]]=-mu[i];            else {                mu[i*prime[j]]=0;                break;            }        }    }}map
       
         mp;ll djs(ll n){    if(n<=maxn) return s[n];    if(mp[n]) return mp[n];    ll ans=1;    for(ll l=2,r;l<=n;l=r+1){        r=n/(n/l);        ll cx=((l+r)%mod)*((r-l+1)%mod)%mod*inv%mod;        ans=(ans-cx*djs(n/l)%mod)%mod;    }    return mp[n]=(ans+mod)%mod;}int main(){    freopen("b.in","r",stdin);    freopen("b.out","w",stdout);    scanf("%lld",&n);    init();    printf("%lld",djs(n));}
       
      

小心爆long long，l、r可能到达1e10；

整除分块的操作也在里面。