# 杜教筛瞎推 学习笔记【杜教筛】【数学】

## 一、例题

### 2.推导

\begin{aligned} \sum_{i=1}^n(f*g)(i)&=\sum_{i=1}^n\sum_{d|i}f(d)g\left(\frac id\right)\\ &=\sum_{i=1}^n\sum_{x=1}^i\sum_{xy=i}f(x)g(y)\\ \end{aligned}

\begin{aligned} \sum_{i=1}^n(f*g)(i)&=\sum_{y=1}^n\sum_{xy\le n}f(x)g(y)\\ &=\sum_{y=1}^ng(y)\sum_{xy\le n}f(x)\\ &=\sum_{y=1}^ng(y)\sum_{i=1}^{\left\lfloor\frac ny\right\rfloor}f(i) \end{aligned}

$$\sum_{i=1}^n(f*g)(i)=\sum_{y=1}^ng(y)S\left(\left\lfloor\frac ny \right\rfloor\right)$$

$$g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{y=2}^ng(y)S\left(\left\lfloor\frac ny\right\rfloor\right)$$

### 3.复杂度

$$T(n)=\sum_{i=1}^\sqrt n \sqrt{\left\lfloor\frac ni\right\rfloor}=\int_1^\sqrt n\sqrt{\frac nx}\mathrm dx$$

\begin{aligned} T(n)&=\int_1^\sqrt n\sqrt n\times x^{-\frac 12}\mathrm dx\\ &=2\sqrt{n\sqrt n}-2\sqrt n\\ &=O\left(n^{\frac 34}\right) \end{aligned}

\begin{aligned} T(n)&=O(n^c)+\int_1^{n^{1-c}}\sqrt n\times x^{-\frac 12}\mathrm dx\\ &=O(n^c)+2\sqrt{n\cdot n^{1-c}}-2\sqrt n\\ &=O(n^c)+O\left(n^{1-\frac c2}\right) \end{aligned}

### 4.构造

\begin{aligned} g(1)S(n)&=\sum_{i=1}^n(f*g)(i)-\sum_{y=2}^ng(y)S\left(\left\lfloor\frac ny\right\rfloor\right)\\ 1\times S(n)&=\sum_{i=1}^n(\varphi*1)(i)-\sum_{y=2}^n1\times S\left(\left\lfloor\frac ny\right\rfloor\right)\\ S(n)&=\frac{n(n+1)}2-\sum_{y=2}^nS\left(\left\lfloor\frac ny\right\rfloor\right) \end{aligned}

### 5.代码

#include<cstdio>
#include<cstring>
#define ll long long
const int mxm=2000000;
int pri[1<<20],cnt=0,n;
ll phi[2000100],mu[2000100];
bool is[2000100];
ll f[2000100],g[2000100];
bool used[2000];
ll calc(int x)
{
if(x<=mxm)
return phi[x];
int t=n/x;
if(used[t])
return g[t];
used[t]=1;
ll ans=(ll)(1ll+x)*x/2;
for(int i=2;i<=x;++i)
{
int nxt=x/(x/i);
ans-=calc(x/i)*(nxt-i+1);
i=nxt;
if(i==2147483647)
break;
}
return g[t]=ans;
}
ll calc1(int x)
{
if(x<=mxm)
return mu[x];
int t=n/x;
if(used[t])
return g[t];
used[t]=1;
ll ans=1;
for(int i=2;i<=x;++i)
{
int nxt=x/(x/i);
ans-=calc1(x/i)*(nxt-i+1);
i=nxt;
if(i==2147483647)
break;
}
return g[t]=ans;
}
int main()
{
is[0]=is[1]=1;
phi[1]=1;
mu[1]=1;
for(int i=2;i<=mxm;++i)
{
if(!is[i])
{
pri[++cnt]=i;
mu[i]=-1;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*pri[j]<=mxm;++j)
{
is[i*pri[j]]=1;
if(i%pri[j]==0)
{
mu[i*pri[j]]=0;
phi[i*pri[j]]=pri[j]*phi[i];
break;
}
else
{
mu[i*pri[j]]=-mu[i];
phi[i*pri[j]]=(pri[j]-1)*phi[i];
}
}
mu[i]+=mu[i-1];
phi[i]+=phi[i-1];
}
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(used,0,sizeof(used));
printf("%lld ",calc(n));
memset(used,0,sizeof(used));
printf("%lld\n",calc1(n));
}
return 0;
}


## 二、练习

### 洛谷 P3768 简单的数学题

\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j)\\ =&\sum_{i=1}^n\sum_{j=1}^nij\sum_{k=1}^nk\cdot[\gcd(i,j)=k]\\ =&\sum_{k=1}^nk\sum_{i=1}^n\sum_{j=1}^nij[\gcd(i,j)=k] \end{aligned}

\begin{aligned} g(k)&=\sum_{k|d}f(d)\\ &=\sum_{k|d}\sum_{i=1}^n\sum_{j=1}^nij[\gcd(i,j)=k,2k,3k,\dots]\\ &=\sum_{i=1}^n\sum_{j=1}^nij[k|\gcd(i,j)]\\ &=\sum_{i=1}^\left\lfloor\frac nk\right\rfloor\sum_{j=1}^\left\lfloor\frac nk\right\rfloor ijk^2\\ &=k^2\frac{\left\lfloor\frac nk\right\rfloor^2\left(\left\lfloor\frac nk\right\rfloor+1\right)^2}4\\\ f(k)&=\sum_{k|d}\mu\left(\frac dk\right)g(d)\\ &=\sum_{i=1}^\left\lfloor\frac nk\right\rfloor\mu(i)g(ki)\\ &=\sum_{i=1}^{\left\lfloor\frac nk\right\rfloor}\mu(i)k^2i^2\frac{\left\lfloor\frac n{ki}\right\rfloor^2\left(\left\lfloor\frac n{ki}\right\rfloor+1\right)^2}4 \end{aligned}

\begin{aligned} &\sum_{k=1}^nkf(k)\\ =&\sum_{k=1}^nk\sum_{i=1}^{\left\lfloor\frac nk\right\rfloor}\mu(i)k^2i^2\frac{\left\lfloor\frac n{ki}\right\rfloor^2\left(\left\lfloor\frac n{ki}\right\rfloor+1\right)^2}4\\ =&\sum_{T=1}^n\sum_{d|T}\mu(d)\frac{T^3}d\frac{\left\lfloor\frac nT\right\rfloor^2\left(\left\lfloor\frac nT\right\rfloor+1\right)^2}4\\ =&\sum_{T=1}^n\left(\sum_{d|T}\mu(d)\frac Td\right)T^2\frac{\left\lfloor\frac nT\right\rfloor^2\left(\left\lfloor\frac nT\right\rfloor+1\right)^2}4 \end{aligned}

#### 推导：

$(\mu*id)(n)=\sum_{d|n}\mu(d)\frac nd$

$$\sum_{T=1}^n\varphi(T)T^2\frac{\left\lfloor\frac nT\right\rfloor^2\left(\left\lfloor\frac nT\right\rfloor+1\right)^2}4$$

\begin{aligned} &((F\cdot G)*(F\cdot H))(n)\\ =&\sum_{d|n}(F\cdot G)(d)\times(F\cdot H)\left(\frac nd\right)\\ =&\sum_{d|n}F(d)\times G(d)\times F\left(\frac nd\right)\times H\left(\frac nd\right)\\ =&F(n)\times \sum_{d|n}G(d)\times H\left(\frac nd\right)\\ =&F(n)\times(G*H)(n)\\ =&(F\cdot(H*H))(n) \end{aligned}

### 1 说点什么

0 Followers

Most reacted comment