• 欢迎光临~

# 杜教筛（基础篇）

### 杜教筛

(f(n))为一积性函数
(S(n)=sum_{i=1}^nf(i))(nleq 10^{10})

[sum_{i=1}^nsum_{d|i}g(d)f(frac{i}{d}) ]

[sum_{d=1}^ng(d)sum_{d|i}f(frac{i}{d}) ]

[sum_{d=1}^ng(d)sum_{d|i}f(frac{i}{d}) ]

[sum_{d=1}^ng(d)sum_{i=1}^{lfloor frac{n}{d}rfloor}f(i) ]

[sum_{d=1}^ng(d)S(lfloor frac{n}{d}rfloor) ]

[g(1)S(n)=sum_{i=1}^nsum_{d|i}g(d)f(frac{i}{d})-sum_{d=2}^ng(d)S(lfloor frac{n}{d}rfloor) ]

[S(n)=frac{sum_{i=1}^nsum_{d|i}g(d)f(frac{i}{d})-sum_{d=2}^ng(d)S(lfloor frac{n}{d}rfloor)}{g(1)} ]

### [BZOJ3944]--Sum

[sum_{i=1}^{n}mu(i) ]

[sum_{i=1}^{n}varphi(i) ]

[S(n)=frac{1-sum_{d=2}^nS(lfloor frac{n}{d}rfloor)}{1} ]

[S(n)=frac{sum_{i=1}^ni-sum_{d=2}^nS(lfloor frac{n}{d}rfloor)}{1} ]

``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4641600;
LL s[N];
LL mu[N];
int v[N],prime[N],tot=0;
LL phi[N];
LL p[N];
void init(int n)
{
phi[1]=1;
mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!v[i])
{
prime[++tot]=i;
v[i]=i;
mu[i]=-1;
phi[i]=i-1;
}
for(int j=1;j<=tot;j++)
{
if(prime[j]>v[i]||i*prime[j]>n) break;
v[i*prime[j]]=prime[j];
if(i%prime[j]==0)
{
mu[i*prime[j]]=0;
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else
{
mu[i*prime[j]]=mu[i]*mu[prime[j]];
phi[i*prime[j]]=1ll*phi[i]*(prime[j]-1);
}
}
}
for(int i=1;i<=n;i++)
mu[i]=mu[i-1]+mu[i];
for(int i=1;i<=n;i++)
phi[i]=phi[i-1]+phi[i];
}
bool vis[N];
LL S(LL n,int k)
{
if(n<=N-10) return mu[n];
if(vis[k]) return s[k];
LL res=1;
LL l=2,r;
for(;l<=n;l=r+1)
{
r=n/(n/l);
res=res-1ll*(r-l+1)*S(n/l,1ll*k*l);
}
vis[k]=1;
s[k]=res;
return res;
}
LL P(LL n,int k)
{
if(n<=N-10) return phi[n];
if(vis[k]) return p[k];
LL res=1ll*(1ll+n)*n/2;
LL l=2,r;
for(;l<=n;l=r+1)
{
r=n/(n/l);
res=res-1ll*(r-l+1)*P(n/l,k*l);
}
vis[k]=1;
p[k]=res;
return  res;
}
int main()
{
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
init(N-10);
int T;
cin>>T;
while(T--)
{
LL n;
cin>>n;
cout<<P(n,1)<<' ';
memset(vis,0,sizeof(vis));
cout<<S(n,1)<<endl;
memset(vis,0,sizeof(vis));
}

return 0;
}
``````

### [HDOJ5608]function

(sum_{i=1}^nf(i))

(f(n)=sum_{d|n}F(d)mu(frac{n}{d}))

[S(n)=frac{sum_{i=1}^ni^2-3i+2-sum_{d=2}^nS(lfloor frac{n}{d}rfloor)}{1} ]

(1^2+2^2+3^2+……n^2=n(n+1)(2n+1)/6)

``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6+7;
const LL mod = 1e9+7;
LL Pow(LL a,LL b)
{
LL res=1;
while(b)
{
if(b&1) res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
LL inv(LL n)
{
return Pow(n,mod-2);
}
LL inv6=Pow(3,mod-2),inv2=Pow(2,mod-2);
LL F(LL n){return (1ll*n*(n+1)/2%mod*(2ll*n+1)%mod*inv6%mod-3*(1+n)*n/2%mod+2*n+mod)%mod;}
int mu[N],prime[N],tot=0;
int v[N];
LL f[N];
void init(int n)
{
mu[1]=1;
f[1]=0;
for(int i=2;i<=n;i++)
{
if(!v[i])
{
v[i]=i;
mu[i]=-1;
prime[++tot]=i;
}
for(int j=1;j<=tot;j++)
{
if(prime[j]>v[i]||i*prime[j]>n) break;
v[i*prime[j]]=prime[j];
if(i%prime[j]==0)
{
mu[i*prime[j]]=0;
break;
}
else mu[i*prime[j]]=mu[i]*mu[prime[j]];
}
}
for(LL d=1;d<=n;d++)
for(LL T=d;T<=n;T+=d)
f[T]=(f[T]+(d*d-3*d+2)%mod*mu[T/d]+mod)%mod;
for(int i=1;i<=n;i++)
f[i]=(f[i-1]+f[i])%mod;
}
LL bin[N],top=0;
int tag[N];
int cnt=0;
unordered_map<LL,LL>s,vis;
LL S(LL n)
{
if(n<=1e6) return f[n];
if(vis[n]) return s[n];
LL res=F(n);
LL l=2,r;
for(;l<=n;l=r+1)
{
r=n/(n/l);
res=res-(1ll*(r-l+1)*S(n/l)%mod);
res=(res%mod+mod)%mod;
}
vis[n]=1;
s[n]=res;
return res;
}
{
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
void write(LL x)
{
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9)
write(x/10);
putchar(x % 10 + '0');
return;
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
init(1e6);
LL T;
cin>>T;
LL n;
while(T--)
{
if(n<=1e6)
{
write(f[n]);
printf("n");
continue;
}
write(S(n));
printf("n");
}
return 0;
}
``````

### 【51nod 2026】Gcd and Lcm

[sum_{i=1}^nsum_{j=1}^nf(gcd(i,j))f(lcm(i,j)) ]

(f(p^k)=1-p)，也就是说对于每个质因子而言，他的指数是多少根本没有关系，因此一个数的(f)只跟他质因子的种类数有关

1：对于(i,j)共有的因子，他们被乘了两次,设他们是A
2：对于(i,j)各自有的因子，他们都只乘了一次，假设分别是B,C

B)(AC)

[sum_{i=1}^nsum_{j=1}^nf(i)f(j) ]

[sum_{i=1}^nf(i)sum_{j=1}^nf(j) ]

[(sum_{i=1}^nf(i))^2 ]

[sum_{i=1}^nsum_{d|i}mu(d)d ]

[sum_{d=1}^nmu(d)dsum_{d|i}^n1 ]

[sum_{d=1}^nmu(d)dlfloor frac{n}{d}rfloor ]

[=sum_{d|n};mu(d)d;g(frac{n}{d}) ]

[=sum_{d|n};mu(d)d;frac{n}{d} ]

[=nsum_{d|n};mu(d) ]

[=e ]

[S(n)=frac{1-sum_{d=2}^niS(lfloor frac{n}{d}rfloor)}{1} ]

``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
const int N =1e6+7;
int mu[N];
LL F[N];
int v[N],prime[N],tot=0;
void init(int n)
{
mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!v[i])
{
v[i]=i;
prime[++tot]=i;
mu[i]=-1;
}
for(int j=1;j<=tot;j++)
{
if(v[i]<prime[j]||i*prime[j]>n) break;
v[i*prime[j]]=prime[j];
if(i%prime[j]==0)
{
mu[i*prime[j]]=0;
break;
}
else mu[i*prime[j]]=mu[i]*mu[prime[j]];
}
}
for(LL i=1;i<=n;i++)
F[i]=(F[i-1]+mu[i]*i%mod)%mod;
}
unordered_map<LL,LL> s,vis;
LL S(LL n)
{
if(n<=1e6) return F[n];
if(vis[n]) return s[n];
LL res=1;
LL l=2,r;
for(;l<=n;l=r+1)
{
r=n/(n/l);
res=(res-(l+r)*(r-l+1)/2%mod*S(n/l)%mod+mod)%mod;
}
vis[n]=1;
s[n]=res;
return res;
}
LL f(LL n)
{
LL l=1,r;
LL ans=0;
for(;l<=n;l=r+1)
{
r=(n/(n/l));
ans=(ans+(S(r)-S(l-1)+mod)%mod*(n/l)%mod)%mod;
}
return ans;
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
init(1e6);
LL n;
cin>>n;
cout<<f(n)*f(n)%mod;
return 0;
}
``````

### 【51Nod 1238最小公倍数之和 V3

[sum_{i=1}^nsum_{j=1}^nlcm(i,j) ]

[= sum_{T=1}^nS(lfloor frac{n}{T} rfloor)S(lfloor frac{m}{T} rfloor)Tsum_{k|T}^Tmu(k)k ]

[sum_{i=1}^nsum_{d|i}imu(d)d ]

[sum_{d=1}^nmu(d)dsum_{d|i}i ]

[sum_{d=1}^nmu(d)dsum_{i=1}^{lfloor frac{n}{d}rfloor}id ]

[sum_{d=1}^nmu(d)d^2sum_{i=1}^{lfloor frac{n}{d}rfloor}i ]

[S(n)=frac{sum_{i=1}^ni-sum_{d=2}^ni^2S(lfloor frac{n}{d}rfloor)}{1} ]

``````#include<bits/stdc++.h>
using namespace std;
const int N = 4641600;
typedef unsigned long long LL;
int mu[N],prime[N],tot=0;
int v[N];
LL F[N];
const LL mod = 1e9+7;
void init(LL n)
{
F[1]=1;
for(int i=2;i<=n;i++)
{
if(!v[i])
{
v[i]=i;
F[i]=1LL*i*((1-i+mod)%mod)%mod%mod;
prime[++tot]=i;
}
for(int j=1;j<=tot;j++)
{
if(prime[j]>v[i]||i*prime[j]>n) break;
v[i*prime[j]]=prime[j];
if(i%prime[j]==0)
{
F[i*prime[j]]=1LL*F[i]*prime[j]%mod;
break;
}
else F[i*prime[j]]=1LL*F[i]*F[prime[j]]%mod;
}
}
for(int i=1;i<=n;i++)
F[i]=(F[i-1]+F[i])%mod;
}
unordered_map<LL,LL>s,vis;
LL Pow(LL a,LL b)
{
LL res=1;
while(b)
{
if(b&1) res=1LL*res*a%mod;
a=1LL*a*a%mod;
b>>=1LL;
}
return res;
}
LL inv6=Pow(6,mod-2),inv2=Pow(2,mod-2);
LL sqr(LL n){n%=mod;return 1LL*n*(n+1)%mod*(2LL*n+1)%mod*inv6%mod;}
LL sum(LL n){n%=mod;return 1LL*(1+n)%mod*n%mod*inv2%mod;}
bool flag=1;
LL Sum(LL n)
{
if(n<=N-10) return F[n];
if(vis[n]) return s[n];
LL res=sum(n);
LL l=2,r;
for(;l<=n;l=r+1)
{
r=n/(n/l);
res=(res-1LL*((sqr(r)-(sqr(l-1)))+mod)%mod*Sum(n/l)%mod+mod)%mod;
}
vis[n]=1;
s[n]=res;
return res;
}
int main()
{
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
init(N-10);
LL n;
cin>>n;
LL ans=0;
LL l=1,r;
for(;l<=n;l=r+1)
{
r=(n/(n/l));
ans=(ans+1LL*sum(n/l)*sum(n/l)%mod*((Sum(r)-Sum(l-1)+mod)%mod)%mod)%mod;
}
cout<<ans;
return 0;
}
``````

### 51【Nod 1237】最大公约数之和 V3

[=sum_{d=1}^nvarphi(d)lfloor frac{n}{d} rfloorlfloor frac{m}{d} rfloor ]

``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
const LL N = 4641600;
LL phi[N];
LL v[N],prime[N],tot=0;
void init(LL n)
{
phi[1]=1;
for(LL i=2;i<=n;i++)
{
if(!v[i])
{
v[i]=i;
phi[i]=i-1;
prime[++tot]=i;
}
for(LL j=1;j<=tot;j++)
{
if(prime[j]>v[i]||i*prime[j]>n) break;
v[i*prime[j]]=prime[j];
if(i%prime[j]==0)
{
phi[i*prime[j]]=1LL*phi[i]*prime[j]%mod;
break;
}
else phi[i*prime[j]]=1LL*phi[i]*(prime[j]-1)%mod;
}
}
for(LL i=1;i<=n;i++)
phi[i]=(phi[i-1]+phi[i])%mod;
}
LL Pow(LL a,LL b)
{
LL res=1;
while(b)
{
if(b&1) res=1LL*res*a%mod;
a=1LL*a*a%mod;
b>>=1;
}
return res;
}
LL inv2=Pow(2ll,mod-2);
unordered_map<LL,LL>vis,s;
LL mul(LL a,LL b)
{
LL res=0;
while(b)
{
if(b&1) res=(res+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return res;
}
LL Sum(LL n)
{
if(n<=N-10) return phi[n];
if(vis[n]) return s[n];
LL res=mul(mul(n,n+1),inv2);
LL l=2,r;
for(;l<=n;l=r+1)
{
r=(n/(n/l));
res=(res-1LL*(r-l+1)%mod*Sum(n/l)%mod)%mod;
}
res=(res+mod)%mod;
vis[n]=1;
s[n]=res;
return res;
}
int main()
{
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
init(N-10);
LL n;
cin>>n;
LL res=0;
LL l=1,r;
for(;l<=n;l=r+1)
{
r=n/(n/l);
res=(res+mul(Sum(r)-Sum(l-1),mul(n/l,n/l))+mod)%mod;
}
cout<<res;
return 0;
}
``````

### [bzoj 4176] Lucas的数论

[ans=sum_{d=1}^nmu(d)sum_{x=1}^{lfloor frac{n}{d} rfloor}lfloor frac{n}{dx} rfloor sum_{y=1}^{lfloor frac{m}{d} rfloor}lfloor frac{m}{dy} rfloor ]

(mu)的部分可以杜教筛处理，后边的部分可以整除分块

``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2500005;
const int mod = 1e9+7;
int mu[N],prime[N],tot=0;
LL v[N];
void init(int n)
{
mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!v[i])
{
v[i]=i;
mu[i]=-1;
prime[++tot]=i;
}
for(int j=1;j<=tot;j++)
{
if(prime[j]>v[i]||i*prime[j]>n) break;
v[i*prime[j]]=prime[j];
if(i%prime[j]==0)
{
mu[i*prime[j]]=0;
break;
}
else mu[i*prime[j]]=mu[i]*mu[prime[j]];
}
}
for(int i=1;i<=n;i++)
mu[i]=(mu[i]+mu[i-1]);
}
unordered_map<LL,LL> s;
LL Sum(LL n)
{
if(n<=N-10) return mu[n];
if(s[n]) return s[n];
LL res=1;
LL l=2,r;
for(;l<=n;l=r+1)
{
r=n/(n/l);
res=(res-1ll*(r-l+1)*Sum(n/l)%mod)%mod;
}
res=(res+mod)%mod;
s[n]=res;
return res;
}
LL S(LL n)
{
int l=1,r;
LL res=0;
for(;l<=n;l=r+1)
{
r=n/(n/l);
res=(res+(LL)(n/l)*(r-l+1)%mod)%mod;
}
return res;
}
int main()
{
freopen("math.in","r",stdin);
freopen("math.out","w",stdout);
init(N-10);
LL n;
cin>>n;
LL res=0;
int l=1,r;
for(;l<=n;l=r+1)
{
r=n/(n/l);
LL val=S(n/l);
res=(res+1ll*val*val%mod*(Sum(r)-Sum(l-1)+mod)%mod)%mod;
}
cout<<res;
return 0;
}
``````