最近几天全在做OI数论题，写个blog记一下套路。
-
例如
要求\(\operatorname g(n)=\sum_{d|n} d\cdot\varphi(\frac{n}{d})\)
尽管你会一个叫做 \(\text{LCMSUM}\)(可跳转) 的题目，这道题最后可以转化为：\(\operatorname g(n)=\sum_{d|n} d\cdot\varphi(d)\)
题解：oi-wiki例题解析
but,两个只是长得像，结论完全不一样
之后在网上的\(\LaTeX\)在线编辑器写了推式子的过程
然后被前面的前面的右边的机位坐着的\(\text{j}\color{Red}{\text{immyywang}}\)单方面
吊着打了
-
又例如
试求\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sigma_1(i\cdot j)\)
然后由于不知道\(\sigma_1(n)\)的性质又挂了，只能翻题解看解答过程。
所以进行一个总结
\(\mathtt{Part}\ \ 1.\mathtt{Dirichlet}\)卷积\(\&\) \(\mathtt{mobius}\)反演
\(\mathsf{1}.\) 入门
-
\(\mathtt{Dirichlet}\)卷积与其性质
若存在 \(f(n)=\sum\limits_{d|n}g(d)\cdot h(\frac nd)\) ，称 \(f(n)\) 为 \(g(n)\) 与 \(h(n)\) 的狄利克雷卷积。
下文中以$* \(表示狄利克雷卷积，\)\times$表示乘积
狄利克雷卷积满足，且有：\(\operatorname f=\operatorname g \iff \operatorname f*\operatorname h=\operatorname g*\operatorname h\).
狄利克雷卷积中，满足:
- 交换律，结合律，分配律
- $ f= g \iff f* h= g* h$.
- \(f*\varepsilon=f\)
- \(\exists g,\forall h,f* h=\varepsilon \iff h=g\)（\(f\)有且仅有一个狄利克雷卷积运算中的逆元）
- \(\color{Red}{f* g=\varepsilon \iff g(n)=\frac{\varepsilon(n)-\sum_{d|n\wedge d\not =1}f(d)g(\frac xd)}{f(1)}}\)
-
积性函数
若 \(f(1)=1 \wedge \forall x,y\in \mathbb{N}^* ,\gcd(x,y)=1\Rightarrow f(xy)=f(x)f(y)\)，则 \(f(x)\) 是一个积性函数。
若 \(f(1)=1 \wedge \forall x,y\in \mathbb{N}^* ,f(xy)=f(x)f(y)\)，则 \(f(x)\) 是一个积性函数。
若有积性函数 \(f(x),g(x)\)，满足：
- \(h(x)=f(x^n)\)是积性函数
- \(h(x)=f^n(x)\)是积性函数
- \(h(x)=f(x)g(x)\)是积性函数
- \(h(x)=f(x)* g(x)=\sum\limits_{d|x} f(d)g(\frac nd)\)是积性函数
对于 \(n=\prod\limits_{p_i\in \mathcal{P}}p_{i}^{\alpha_i}\)：
- \(f(x)\) 为积性函数 \(\Rightarrow f(n)=\prod\limits_{p_i\in \mathcal{P}}f(p_i^{\alpha_i})\)
- \(f(x)\) 为完全积性函数 \(\Rightarrow f(n)=\prod\limits_{p_i\in \mathcal{P}}f(p_i)^{\alpha_i}\)
常见积性函数：
- 完全积性函数
- \(\varepsilon(n)=[n=1]\)
- \(\operatorname {id}_ k(n)=n^k\)
- \(1(n)=1\)
- 积性函数
- \(\varphi(n)=\sum\limits_{i=1}^n\varepsilon(\gcd(i,n))\)
- \(\sigma_k(n)=\sum\limits_{d|n}d^k\)
- \(\mu(n)=\begin{cases}1&n=1\\0&\exists d>1,d^2|n\\(-1)^{\omega(n)}&\text{otherwise}\end{cases}\)
- 加性函数(\(\forall x,y\in \mathbb{Z},\gcd(x,y)=1\Rightarrow f(xy)=f(x)+f(y)\))
- \(\omega(n)=|\{x\in \mathcal{P}\mid x|n\}|\)
其中\(\operatorname {id}_ 1(n)\rightarrow \operatorname {id}(n),\sigma_0(n)=d(n)=\tau(n),\sigma_1(n)\rightarrow\sigma(n)\)
\(\color{Red}{\text{一般性规律}}\)
- \(\color{Red}{\varepsilon=\mu * 1}\)
- \(\color{Red}{d=1* 1}\)
- \(\color{Red}{\sigma=\operatorname {id}* 1}\)
- \(\color{Red}{\varphi=\mu*\operatorname {id},\varphi* 1=\operatorname {id}}\)
- \(\color{Red}{d(i\cdot j)=\sum\limits_{x|i}\sum\limits_{y|j}\varepsilon(\gcd(x,y))}\)
- \(\color{Red}{\varphi(i\cdot j)=\dfrac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}}\)
\(\mathsf{2}.\) 莫比乌斯反演入门
-
前置知识
数论分块：快速计算包含向下取整，形如\(\sum\limits_{i=1}^{n}f(i)g(\left\lfloor\frac {n}{i}\right\rfloor)\)的和式。
可以 \(\text O(1)\) 计算 \(f(r)-f(l)\) 或者 可进行 \(f(n)\) 前缀和预处理时使用。
时间复杂度为 \(\text O(\sqrt n)\)
一维数论分块模板如下（请各位自行忽略码风）：
ll ans=0;
for(ll l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
ans+=(f(r)-f(l-1))*(n/l);
}
当 \(f(r)-f(l-1)\) 时间有些紧时，可以以空间换时间做优化。
ll ans=0,las=f(1),cur=0;
for(ll l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
cur=f(r);
ans+=(cur-las)*(n/l);
las=cur;
}
若是选择对 \(f(n)\) 进行前缀和预处理，往往结合筛法。
二维数论分块模板如下： \(\sum\limits_{i=1}^{\min(n,m)}\left\lfloor\frac {n}{i}\right\rfloor\left\lfloor\frac {m}{i}\right\rfloor\)
if(n>m) swap(n,m);
ll ans=0;
for(ll l=1,r;l<=n;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans+=(f(r)-f(l-1))*(n/l);
}
正确性证明上转 \(\text{OI-wiki}\)。
正文
一句话：\(\color{Red}{f*\mu=g\iff f=g* 1}\)
具体来说：
\(\begin{cases}f(n)=\sum\limits_{d|n}g(d)\iff g(n)=\sum\limits_{d|n}\mu(\frac nd)f(d)\\
f(n)=\sum\limits_{n|d}g(d)\iff g(n)=\sum\limits_{n|d}\mu(\frac dn)f(d)\end{cases}\)
典例：
-
\(\color{Red}{\sum\limits_{i=1}^n\sum\limits_{j=1}^m [\gcd(i,j)=k]}\)
\(\begin{aligned} \text{原式}&=\sum\limits_{i=1}^{\left\lfloor\frac {n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[\gcd(i,j)=1]\\&(\gcd(i,j)=k\\ &\Rightarrow let:\ i=i'\times k,j=j'\times k\\ &\Rightarrow\gcd(i'\cdot k,j'\cdot k)=k*\gcd(i',j'))\\ &=\sum\limits_{i=1}^{\left\lfloor\frac {n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}\sum\limits_{d|\gcd(i,j)}\mu(d)&(\varepsilon = \mu* 1)\\ &=\sum\limits_{d=1}\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac {n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[d\mid i]\times[d\mid j]\\ &=\sum\limits_{d=1}\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac {n}{k}\right\rfloor}[d\mid i]\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[d\mid j]\\ &=\sum\limits_{d=1}^{\min(\left\lfloor\frac {n}{k}\right\rfloor,\left\lfloor\frac {m}{k}\right\rfloor)}\mu(d)\left\lfloor\frac {n}{kd}\right\rfloor\left\lfloor\frac{m}{kd}\right\rfloor\\ \end{aligned}\)
数论分块解决。
常见套路：
- 提出 \(\gcd(i,j)\)
- 调换求和顺序
又例：P6156 简单题
要求\(\sum\limits_{i=1}^n\sum\limits_{j=1}^n(i+j)^k\mu(\gcd(i,j))^2\gcd(i,j)\)，其中\(n\in[1,5\times 10^6],k\in[1,10^{18}]\)
首先将 \(\gcd(i,j)\) 提前，写成 \(\sum\limits_{d}\sum\limits_{i=1}^n\sum\limits_{j=1}^n[\gcd(i,j)=d](i+j)^k\mu(d)^2d\)
然后向上面一样例行公事。
\(\sum\limits_{d}\sum\limits_{i=1}^{\left\lfloor\frac nd\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac nd\right\rfloor}[\gcd(i,j)=1](id+jd)^k\mu(d)^2d\)
把 \(d\) 从括号中提出，调换一下顺序。
\(\sum\limits_{d}d^k\mu(d)^2d\sum\limits_{i=1}^{\left\lfloor\frac nd\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac nd\right\rfloor}(i+j)^k[\gcd(i,j)=1]\)
出现了一个 \(\varepsilon\)，明显需要莫比乌斯反演：
\(\sum\limits_{d}d^k\mu(d)^2d\sum\limits_{i=1}^{\left\lfloor\frac nd\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac nd\right\rfloor}(i+j)^k\sum\limits_{p|gcd(i,j)}\mu(p)\)
再次调换顺序，把括号里的 \(p\) 同样提出来。
\(\sum\limits_{d}\sum\limits_{p}d^{k+1}\mu(d)^2\mu(p)p^k \sum\limits_{i=1}^{\left\lfloor\frac n{dp}\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac n{dp}\right\rfloor}(i+j)^k\)
对于后面的部分，我们可以放一放，最后看能不能化简，
先把这部分设为 \(\alpha(n)=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\)
原式写成
\(\sum\limits_{d}\sum\limits_{p}{dp}^k\mu(p)\mu(d)^2d
\alpha(\left\lfloor\frac n{dp}\right\rfloor)\)
发现这里面有很多的 \(dp\) 啊，还是要改一下下标的，我们设 \(dp=T\)。
\(\sum\limits_{T=1}^n\sum\limits_{d|T}T^k\mu(\frac Td)\mu(d)^2d \alpha(\left\lfloor\frac nT\right\rfloor)= \sum\limits_{T=1}^n\alpha(\left\lfloor\frac nT\right\rfloor)T^k\sum\limits_{d|T}\mu(\frac Td)\mu(d)^2d \)
明显我们只需要求后半部分 \(\sum\limits_{d|T}\mu(\frac Td)\mu(d)^2d\) 的前缀和就可以利用数论分块解决了。
后半部分是一堆积性函数的狄利克雷卷积，明显是一个积性函数，能用筛法。
这部分可以先看下面筛法的引入与举例子部分再看接下来的过程。
设 \(\beta(n)=\sum\limits_{d|n}\mu(\frac nd)\mu(d)^2d\) 还是三部曲走：
- \(n=1\)时，\(\beta(1)=1\)
- \(n\in prime\)时，\(\beta(n)=n-1\)
- \(\mu(n)=0\)时，同样需要推理 \(\beta(p^q)\ ,\ p \in prime \ ,\ q\in \mathbb{N}\cap\left[2,+\infty\right]\)，这里需要分类讨论
- \(q=2\)，此时通过枚举每一项可知 \(\beta(p^2)=-p\)，
- \(q\in \mathbb{N}\cap\left[3,+\infty\right]\)，此时 \(\mu(p^{q-i})\) 和 \(\mu(p^i)\) 中至少有一个为 \(0\)，故 \(\beta(p^q)=0\)
以此进行筛法并求出前缀和即可。
接下来处理 \(\alpha(n)\)，设\(\gamma(n)=\sum_{i=1}^ni^k\)
\(\begin{aligned} \alpha(n)&=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\\ &=\sum_{i=1}^n \sum_{j=1}^{n+i}j^k-\sum_{j=1}^ij^k\\ &=\sum_{i=1}^n \gamma(n+i)-\gamma(i)\\ &=\sum_{i=1}^{2n}\gamma(i)-2\sum_{i=1}^n\gamma(i) \end{aligned}\)
记录 \(\gamma(n)\) 的前缀和即可。
但是啊，这题卡掉了\(O(n\log k)\)的做法，所以甚至求 \(i^k\) 都需要使用筛法。
数论分块解决。
-
莫比乌斯反演的扩展形式
若有数论函数 \(\alpha(n),\beta(n)\) 满足 \(\alpha*\beta=\varepsilon\) 且 \(z(n)\) 为完全积性函数，则对于在 \(\left[1,+\infty\right)\) 上有定义的函数（对的，它不需要是个数论函数） \(f(n),g(n)\) 有\(g(n)=\sum\limits_{i\in [1,n]}z(i)\alpha(i)f(\frac ni)\iff f(n)=\sum\limits_{i\in [1,n]}z(i)\beta(i)g(\frac ni)\iff\)
\(\mathsf{3}.\) 莫比乌斯反演进阶
我们知道有一个PPT叫做炫酷反演魔术，上面提到一类题目：
\[a_i=\sum\limits_{j=1}^nf(\gcd(i,j))g(i)h(j)\cdot x_j \]已知序列 \(a_{1-n}\) 求 \(x_{1-n}\)
对的，我要再理一遍其中的过程，会的请直接跳过。
首先我们看见这里是已知总和求分项，必然是需要反演的。
我们假设有函数\(\alpha(n)\)满足\(f(n)=\sum_{d|n}\alpha(d)\)
使用莫比乌斯反演(First)
所以\(\alpha(n)=\sum\limits_{d|n}\mu(\frac nd)f(d)\)
然后根据\(\alpha(n)\)的定义，可以知道\(a_i=\sum\limits_{j=1}^n\sum\limits_{d|gcd(i,j)}\alpha(d)g(i)h(j)x_j\)
由于\(d|\gcd(i,j) \iff d|i \land d|j\)，且\(\sum\limits_{i\in \{x\in A|p(x)\}}f(i)=\sum\limits_{i\in A}[p(i)]f(i)\)
所以\(a_i=\sum\limits_{j=1}^n\sum\limits_d[d|i][d|j]\alpha(d)g(i)h(j)x_j\)
运用交换律：\(a_i=g(i)\sum\limits_d\alpha(d)[d|i]\sum\limits_{j=1}^n[d|j]h(j)x_j\)
我们再设\(\beta(d)=\sum\limits_{j=1}^n[d|j]h(j)x_j\)
\(\begin{aligned}\therefore a_i&=g(i)\sum\limits_d\alpha(d)[d|i]\beta(d)\\\frac{a_i}{g(i)}&=\sum\limits_{d|i}\alpha(d)\beta(d)\end{aligned}\)
这里我们还是已知总和求分项
然后使用莫比乌斯反演(Second)
\(\dfrac{a_i}{g(i)}=\sum\limits_{d|i}\alpha(d)\beta(d)\)
\(\alpha(i)\beta(i)=\sum\limits_{d|i}\mu(\frac id)\frac{a_d}{g(d)}\)
\(\beta(i)=\dfrac{\sum\limits_{d|i}\mu\left(\dfrac id\right)\dfrac{a_d}{g(d)}}{\alpha(i)}\)
带回\(\alpha(n)\)和\(\beta(n)\)的定义与推论，即：\(\alpha(n)=\sum\limits_{d|n}\mu(\frac nd)f(d)\)
得：
\(\sum\limits_{j=1}^n[i|j]h(j)x_j=\dfrac{\sum\limits_{d|i}\mu\left(\dfrac id\right)\dfrac{a_d}{g(d)}}{\sum\limits_{d|i}\mu\left(\dfrac id\right)f(d)}\)
明显地，已知总和求分项，明显还是反演
因为：\(\begin{aligned}\sum\limits_{j=1}^n[i|j]h(j)x_j&=\sum\limits_{j}[j\in[1,n]]\cdot[i|j]h(j)x_j\\&=\sum_{i|j}[1\le j\le n]h(j)x_j\end{aligned}\)
所以此处应有莫比乌斯反演(Third)
\([1\le i\le n]h(i)x_i=h(i)x_i=\sum\limits_{i|k}\mu\left(\dfrac ki\right)\left(\dfrac{\sum\limits_{d|k}\mu\left(\dfrac kd\right)\dfrac{a_d}{g(d)}}{\sum\limits_{d|k}\mu\left(\dfrac kd\right)f(d)}\right)\)
\(\therefore x_i=\frac{\sum\limits_{i|k}\mu\left(\frac ki\right)\left(\frac{\sum\limits_{d|k}\mu\left(\frac kd\right)\frac{a_d}{g(d)}}{\sum\limits_{d|k}\mu\left(\frac kd\right)f(d)}\right)}{h(i)}\)
什么玩意这么丑
化简一下：
\(\therefore x_i=\sum\limits_{i|k}\dfrac{\mu\left(\frac ki\right)}{h(i)}\cdot\dfrac{\sum\limits_{d|k}\mu\left(\frac kd\right)\dfrac{a_d}{g(d)}}{\sum\limits_{d|k}\mu\left(\frac kd\right)f(d)}\)
\(\mathtt{Part}\ \ 2.\) 筛法
用于处理积性函数求值问题，有埃氏筛与线性筛等。下文皆以线性筛为例。
对了前方会出现代码框，是白色的，请各位注意闪光弹
\(\mathsf{A}\). 引入
我们知道对于一个积性函数，有 \(f(a)f(b)=f(ab)\ \ \ (\gcd(a,b)=1)\).
针对这种东西OI有筛法.
观察筛法模板：
#define ll long long
bool isprime[Size];
vector<ll>prime;
ll f[Size];
/*sth to get*/
void pre(ll n)
{
isprime[1]=1;
f[1]=/*sth*/;
for(int i=2;i<=n;i++)
{
if(!isprime[i]) prime.pb(i),f[i]=/*sth*/;
for(auto p:prime)
{
if(i*p>n) break;
isprime[i*p]=1;
if(i%p==0)
{
f[i*p]=/*sth*/;
break;
}
f[i*p]=f[i]*f[p];
}
}
}
其中的注释是一般使用筛法线性时间求一特定积性函数是所需要填写的部分。
要填写的部分一般分为积性函数（此处设该函数为 \(\operatorname f(x)\)）的三种情况：
- \(x=1\)
- \(x\in prime\)
- \(\mu(x)=0\)
一共需要推出三个式子，依次对应上方代码中的三个/* sth */的位置。
这里的三个式子的分类是仿照oi-wiki推筛法式子的方式拟定的。
\(\mathsf{B}\).推式子举例
我们等等再讲\(\text{j}\color{Red}{\text{immyywang}}\)的高级通法。先来几个十分愉悦身心的简单模板。
1. \(\varphi(n)\)
按照上面一步步来。
- \(n=1\)时，\(\varphi(1)=1\)
- \(n\in prime\)时，\(\varphi(n)=n-1\)
- \(\mu(n)=0\)时，\(\varphi(n)=\varphi(\frac np)\cdot p\)
于是乎：
#define ll long long
bool isprime[Size];
vector<ll>prime;
ll phi[Size];
void pre(ll n)
{
isprime[1]=1;
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!isprime[i]) prime.pb(i),phi[i]=i-1;
for(auto p:prime)
{
if(i*p>n) break;
isprime[i*p]=1;
if(i%p==0)
{
phi[i*p]=phi[i]*p;
break;
}
phi[i*p]=phi[i]*phi[p];
}
}
}
2. \(\mu(n)\)
直接根据分类：
- \(n=1\)，\(\mu(1)=1\)
- \(n\in prime\)，\(\mu(n)=-1\)
- \(\mu(n)=0\)，\(\mu(n)=0\)
只能说莫比乌斯的广泛性。
#define ll long long
bool isprime[Size];
vector<ll>prime;
ll mu[Size];
void pre(ll n)
{
isprime[1]=1;
mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!isprime[i]) prime.pb(i),mu[i]=-1;
for(auto p:prime)
{
if(i*p>n) break;
isprime[i*p]=1;
if(i%p==0)
{
mu[i*p]=0;
break;
}
mu[i*p]=mu[i]*mu[p];
}
}
}
3. \(\sigma_{k}(n)=\sum_{d|n} d^k\)
- \(n=1\)，\(\sigma_{k}(1)=1\)
- \(n\in prime\)，\(\sigma_{k}(n)=1+n^k\)
- \(\mu(n)=0\)，\(\sigma_{k}(n\cdot p)=\sigma_{k}(n)\times p+1\)
#define se second
#define ll long long
bool isprime[Size];
vector<ll>prime;
ll si[Size];
void pre(ll n)
{
ll k=2;
si[1]=1;isprime[1]=1;
for(int i=2;i<=n;i++)
{
if(!isprime[i]) prime.pb(i),si[i]=1+ksm(i,k);
for(auto p:prime)
{
if(i*p>n) break;
isprime[i*p]=1;
if(i%p==0)
{
si[i*p]=si[i]*p+1;
break;
}
si[i*p]=si[i]*si[p];
}
}
}
\(\mathsf{C}\). 不一样的式子
以上面的两个相似的函数为例子。
记：
\(\operatorname f(n)=\sum\limits_{d|n} d\cdot \varphi(d)\)
\(\operatorname g(n)=\sum\limits_{d|n} d\cdot \varphi(\frac nd)\)
我们来试试把他们如上的四种情况做一做。
1. \(\operatorname f(n)=\sum\limits_{d|n} d\cdot \varphi(d)\)
- \(n=1\)
此时\(\operatorname f(1)=\sum\limits_{d|1} d\cdot \varphi(d)=1\cdot \varphi(1)=1\)
- \(n\in prime\)
此时
\(\begin{aligned}{} \operatorname f(n)&=\sum_{d|n} d\cdot \varphi(d)\\ &= 1\cdot \varphi(1)+n\cdot \varphi(n)\\ &= 1+n(n-1)\\ \end{aligned}\)
- \(\mu(n)=0\)
为了解决这一情况，我们还需要推理 \(\operatorname f(p^q)\ ,\ p \in prime \ ,\ q\in \mathbb{N}\cap\left[2,+\infty\right]\) 的递推式。
\(\begin{aligned} \operatorname f(p^q)&=\sum_{d|p^q} d\cdot \varphi(d)\\ &=\sum_{i=0}^{q} p^i\cdot \varphi(p^i)\\ &=1+\sum_{i=1}^{q} p^i\cdot (p^{i-1}\times(p-1))\\ &=1+(p-1)\sum_{i=1}^{q} p^{2i-1}\\ \therefore \operatorname f(p^{q+1})&=1+(p-1)\sum_{i=1}^{q+1} p^{2i-1}\\ &=\operatorname f(p^q)+(p-1)p^{2q+1} \end{aligned}\)
我们假设 \(n=i\times p,i=a\times p^q\)，其中 \(p\) 表示 \(i\) 的最小质因子。满足\(\gcd(a,p)=1,q\ge 1\)
\(\begin{aligned} \because \operatorname f(p^{q+1})&=&&\operatorname f(p^q)+(p-1)p^{2q+1}\\ \therefore \operatorname f(p^{q+1})-\operatorname f(p^q)&=&&(p-1)p^{2q+1}\\ \therefore \operatorname f(p^{q+1})\cdot\operatorname f(a)-\operatorname f(p^q)\cdot\operatorname f(a)&=&&(p-1)p^{2q+1}\cdot\operatorname f(a) \end{aligned}\)
同理，\(\operatorname f(p^q)\cdot\operatorname f(a)-\operatorname f(p^{q-1})\cdot\operatorname f(a)=(p-1)p^{2q-1}\cdot\operatorname f(a)\)
\(\begin{aligned} \therefore \operatorname f(a)&=&&\frac{\operatorname f(p^q)\cdot\operatorname f(a)-\operatorname f(p^{q-1})\cdot\operatorname f(a)}{(p-1)p^{2q-1}}\\ \operatorname f(p^{q+1})\times\operatorname f(a)-\operatorname f(p^q)\times\operatorname f(a)&=&&(p-1)p^{2q+1}\cdot\frac{\operatorname f(p^q)\cdot\operatorname f(a)-\operatorname f(p^{q-1})\cdot\operatorname f(a)}{(p-1)p^{2q-1}}\\ &=&&p^2\cdot\operatorname f(p^q)\cdot\operatorname f(a)-p^2\cdot\operatorname f(p^{q-1})\cdot\operatorname f(a)\\ \because \gcd(a,p) &=&& 1\\ \therefore \operatorname f(p^{q+1})\cdot \operatorname f(a)&=&&\operatorname f(i\cdot p)\\ &=&&\operatorname f(n)\\ \operatorname f(p^q)\cdot \operatorname f(a)&=&&\operatorname f(i)\\ \operatorname f(p^{q-1})\cdot \operatorname f(a)&=&&\operatorname f(\frac ip)\\ \end{aligned}\)
依照上三个式子对于\((1)\)式代换，可得：
\(\operatorname f(i\cdot p)-\operatorname f(i)=(\operatorname f(i)-\operatorname f(\frac ip))\times p^2\)
略加调换：
\[\operatorname f(i\cdot p)=\operatorname f(i)+(\operatorname f(i)-\operatorname f(\frac ip))\times p^2 \]得到代码：
#define ll long long
bool isprime[Size];
vector<ll>prime;
ll f[Size];
void pre(ll n)
{
isprime[1]=1;
f[1]=1;
for(int i=2;i<=n;i++)
{
if(!isprime[i]) prime.pb(i),f[i]=1+i*(i+1);
for(auto p:prime)
{
if(i*p>n) break;
isprime[i*p]=1;
if(i%p==0)
{
f[i*p]=f[i]+(f[i]-f[i/p])*p*p;
break;
}
f[i*p]=f[i]*f[p];
}
}
}
2.\(\operatorname g(n)=\sum\limits_{d|n} d\cdot \varphi(\frac nd)\)
- \(n=1\)
此时\(\operatorname g(1)=\sum\limits_{d|1} d\cdot \varphi(\frac nd)=1\cdot \varphi(1)=1\)
- \(n\in prime\)
此时
\(\begin{aligned}{} \operatorname g(n)&=\sum_{d|n} d\cdot \varphi(\frac nd)\\ &= 1\cdot \varphi(1)+n\cdot \varphi(1)\\ &= (n-1)+n\\ &= 2n-1 \end{aligned}\)
- \(\mu(n)=0\)
这个部分做的我心肺骤停。
同样，先确定 \(\operatorname g(p^q)(p\in prime,q\in \mathbb{N})\) 的递推式。
设 \(n = p^q , p \in prime ,q\in \mathbb{N}\cap\left[2,+\infty\right]\)
\( \begin{aligned} g(n) & = \sum_{d \mid n} d \varphi\left(\frac{n}{d}\right) \\ & = \sum_{i = 0}^{q} p^{i} \varphi\left(\frac{p^{q}}{p^{i}}\right) \\ & = \sum_{i = 0}^{q} p^{i} \varphi\left(p^{q-i}\right) \\ \because \varphi\left(p^{q-i}\right) & =\left\{ \begin{array}{l}p^{q-i-1} \times(p-1)&,q-i\geq 1 \\ 1&, q-i = 0\end{array}\right.\\ \therefore g\left(p^{q}\right) & = p^{q}+\sum_{i = 0}^{q-1} p^{i} \cdot p^{q-i-1} \cdot(p-1)\\ & = p^{q}+\sum_{i = 0}^{q-1} p^{q-1} \cdot(p-1) \\ & = p^{q}+(p-1) \cdot q \cdot p^{q-1} \\ \because g\left(p^{q+1}\right) & = p^{q+1}+(p-1) \cdot(q+1) \cdot p^{q} \\ \therefore g\left(p^{q+1}\right) & = g\left(p^{q}\right) \cdot p+p^{q} \cdot(p-1) \\ \end{aligned} \)
随后如同推 \(\operatorname f(n)=\operatorname f(i\times p^q)\) 一样，取出该递推式的 \(q\) 取得 \(q\) 和 \(q-1\) 的情况，
\(\begin{aligned} g\left(p^{q+1}\right) & = g\left(p^{q}\right) \cdot p+p^{q} \cdot(p-1)\\ g\left(p^q\right) & = g\left(p^{q-1}\right) \cdot p+p^{q-1} \cdot(p-1) \end{aligned}\)
两边同乘 \(\operatorname g(a)\)
\( \begin{aligned} g\left(p^{q+1}\right) \cdot g(a) & = g\left(p^{q}\right) \cdot p \cdot g(a)+p^{q} \cdot(p-1) \cdot g(a) \\ g\left(p^{q}\right) \cdot g(a) & = g\left(p^{q-1}\right) \cdot p \cdot g(a)+p^{q-1} \cdot(p-1) \cdot g(a) \\ \end{aligned} \)
代入消元，消去 \(\operatorname g(a)\)
\(\begin{aligned} g(i)-g\left(\frac{i}{p}\right) \times p & = p^{q-1} \cdot(p-1) \cdot g(a) \\ g(a) & = \frac{g(i)-g\left(\frac{i}{p}\right) \cdot p}{p^{q-1} \cdot(p-1)} \\ \therefore g(i \cdot p) & = g(i) \cdot p+\left(g(i)-g\left(\frac{i}{p}\right) \cdot p\right) \cdot p \\ \end{aligned} \)
调整一下，得到最终结果
\(\begin{aligned} g(i\cdot p)& = 2 g(i) \cdot p-g\left(\frac ip\right) \cdot p^{2} \\ \end{aligned} \)
然后填入代码
#define ll long long
bool isprime[Size];
vector<ll>prime;
ll M[Size];
void pre(ll n)
{
isprime[1]=1;
M[1]=1;
for(int i=2;i<=n;i++)
{
if(!isprime[i]) prime.pb(i),M[i]=(2*i-1)%Mod;
for(auto p:prime)
{
if(i*p>n) break;
isprime[i*p]=1;
if(i%p==0)
{
M[i*p]=2*M[i]*p+(M[i]-M[i/p]*p)*p;
break;
}
M[i*p]=M[i]*M[p];
}
}
}
总结该方法：
- 唯一优点：题目如果留够线性筛空间，不会被卡（当然有人卡空间把筛卡了也有可能会 \(\operatorname G\) ，但目前没有出现这一情况）
- 缺点：推式子极其麻烦，推完还容易出错，错了还难查错。
因此就有了我推错式子之后被\(\text{j}\color{Red}{\text{immyywang}}\)吊打的情况出现。
\(\mathsf{IV}\). \(\text{j}\color{Red}{\text{immyywang}}\)通法
等不及了((¯﹃¯))
遇到上面那个十分令人情绪波动产生较大变化的函数，我们就不可能希望如同上面一点点推筛法式子了。
更何况有些时候是让你先推导出数论分块的式子，还要再像上面一样极其复杂的推非常的不人性且不现实。
其实主要都是由于心态出现大问题
这个时候\(\text{j}\color{Red}{\text{immyywang}}\)的通法就起作用了。
但其实OI-wiki上有这部分内容，是我不够细/kk
周知众所，线性筛中 \(i\) 一定是被它的最小质因子 \(p\) 筛掉的。
而 \(i\) 一定可以写为 \(i=a\times p^q\) 的形式，
其中 \(a\in \mathbb{N}\cap\left[1,+\infty\right]\)，\(p=\min_{d|n \wedge d\in prime} d\)，\(\gcd(a,p)=1\).
所以 \(\gcd(a,p^q)=1\).
又因为 \(\gcd(a,b)=1\)时，\(f(ab)=f(a)\cdot f(b)\).
所以对于每一个数，维护 \(i=a\times p^q\) 当中 \(p^q\) 的值即可。
然后你做完了。
过程只需要上方图片至 \(\operatorname g(p^{q+1})=\operatorname g(p^q)\cdot p+p^q\cdot (p-1)\) 为止
这不是薄纱我
下方为上面 \(3.2\) 举例： \(\operatorname g(n)=\sum\limits_{d|n} d\cdot \varphi(\frac nd)\) 的通用筛法代码
bool isprime[Size];
vector<ll>prime;
ll qp[Size];
ll f[Size];
void pre(ll n)
{
isprime[1]=1;
qp[1]=1;f[1]=1;
for(int i=2;i<=n;i++)
{
if(!isprime[i]) prime.pb(i),qp[i]=i,f[i]=2*i-1;
for(auto p:prime)
{
if(i*p>n) break;
isprime[i*p]=1;
if(i%p==0)
{
qp[i*p]=qp[i]*p;
if(i==qp[i])
f[i*p]=f[i]*p+qp[i]*(p-1);
else f[i*p]=f[i/qp[i]]*f[qp[i*p]];
break;
}
qp[i*p]=p;
f[i*p]=f[i]*f[p];
}
}
}
总结：
- 优点：容易，好记，易查错。
- 缺点：除了空间，没有缺点。