莫比乌斯反演与数论函数

本博客的第一篇博文哦!纪念。 #### ---- 莫比乌斯反演，本质是利用莫比乌斯函数与其他函数间卷积关系，对函数做一系列简化，从而更高效的解决问题。 #### ---- 数论函数,更广阔的天地,因为$\mu∈\text{数论函数}$ # 0.写在前面 这里面式子可能比较多,大家多看看证明,尤其是关键证明以及题目推导过程,**硬记下的结论越少,越不容易忘记**。 (看不清式子可以放大网页) 由于写的时候匆忙,公式可能有错误,请私信或者在下方评论。 每个新东西提出后都会做题或者证明,权当熟悉。 ~~不是一个下午就能看懂的,千万不要直接弃疗~~ - 给大家简要介绍一下符号的意思。 有时候以$(a,b)$简写$gcd(a,b)$。 $\lfloor a\rfloor$表示下取整,比如$\lfloor 2.33\rfloor=2$ $[???]$表示 : 如果$???$为真,则值为1,否则为0.(就像if里面的东西) 比如 $[(8,6)>2]=0;\ [233=233]=1$ $a|b$表示$a$是$b$的因数,注意,前面是后面的因数。 比如 $[2|4]=1;\ [2|3]=0$ $\sum$称为**和式**,意思是对……求和。 比如说$\sum\limits_{i}[1\leq i\leq n]i$,表示枚举变量 $i$,对 $[1\leq i\leq n]i$ 求和。 等价于: ```cpp int ans=0; for (int i=1;i<=n;i++) ans+=i; ``` 我们常把上界写在上面,下界写在下面,如$\sum\limits_{i=1}^ni=1+2+3+...+n$ 有$\sum\limits_{d|6}d=1+2+3+6$ (枚举$6$的因数) # 1.狄利克雷卷积与数论函数 ——介绍了狄利克雷卷积,数论函数(积性函数)的综合 $\color{blue}\text{定义:}$ 数论函数,就是**值域为整数**(陪域为复数,但这不重要)的函数。 也就是说下面出现的数没有特殊说明的话,**都是整数**。 两个**数论函数**的**狄利克雷卷积**是一个**新函数**。 比如$f(n),g(n)$两个函数的狄利克雷卷积写作$\Large{f*g}$ (相当于函数名称)。 什么意思呢? $\color{blue}\text{定义:}$ $\large{(f*g)(n)=\sum\limits_{d|n}f(d)g(n/d)}$ 换句话说就是$\large{(f*g)(n)=\sum\limits_{x*y=n}f(x)g(y)}$ (不过一般不这样写,因为不方便化式子。) 比如说计算$(f*g)(10)$ 可得$f(1)g(10)+f(2)g(5)+f(5)g(2)+f(10)g(1)$ (对于某个新东西,能做到的话,理解的最好方式就是手动模拟) 狄利克雷卷积满足以下运算规律(显而易见,不证)： 交换律——$f*g=g*f$; 结合律——$(f*g)*h=f*(g*h)$; (狄利克雷卷积是一个对称的结构) 下面的推导都基于狄利克雷卷积,有必要好好理解。 介绍几个简单的数论函数,让你有个基本概念。 $I(n)$ 无论$n$是啥,它永远等于1,所以叫做~~废柴~~**恒等函数** $ϵ(n)$(也作$e(n)$) 当n=1时,函数值为1,否则为0。被称作**元函数**因为它是卷积的单位元($ϵ*f=f$)。**(Important)** $id(n)=n$ 被称作**单位函数** 附:$id^x(n)=n^x$ 被称作**幂函数**($id(n)$是$id^x(n)$的特殊情况) $e(n),I(n),id(n)$是完全积性函数。 $\color{blue}\text{定义:}$**完全积性函数**: 对于**任意**的整数a和b有$I(ab)=I(a)I(b)$ 附上两个后面会讲的稍微复杂的例子: $\varphi(n)$ 小于n的整数中,与n**互质**的数的**个数**,称作**欧拉函数**(`$\varphi(n)$`)。 $\mu(n)$ 称作**莫比乌斯函数**(`$\mu(n)$`)。 $φ(n)$和$\mu(n)$函数是积性函数(我们后面会证明)。 $\color{blue}\text{定义:}$**积性函数**: 对于一个函数$F$ , 如果$(a,b)=1$时有$F(ab)=F(a)F(b)$,则该函数是积性函数。 积性函数有许多优良性质哦,这些重要的性质我们后面会讲。 很明显,**完全积性函数∈积性函数**。 下面是一些性质: - 对于一个积性函数$F$,有$F(1)=1$ $\color{blue}\text{证明:}$ 根据$F(1)=F(1)F(1)$(定义)可得$F(1)=1$。 - 对于函数$F$,积性$→F(x)=F(p_1^{k_1})F(p_2^{k_2})...F(p_m^{k_m})$ 这里的$p_1...p_m$是指$x$的$m$个**素**因子,也就是把$x$分解的结果。 $k_1...k_m$则是$p_1...p_m$对应的次数。 (比方说1800的分解结果就是$2^3*3^2*5^2$) $\color{blue}\text{证明:}$ 因为$p_1^{k_1},p_2^{k_2},...,p_m^{k_m}$都互质,根据积性易证。 用处:形如$F(prime^k)$的函数值是比较好分析的,我们在利用这个性质来分析一般的情况,后面你们会见到例子。 - 两个积性函数的卷积还是积性函数。 (初学者可以先跳过证明) 设两个积性函数$F_1(x),F_2(x)$。 它们的狄利克雷卷积是$G(n)=\sum\limits_{d|n}F_1(d)F_2(n/d)$ $\color{blue}\text{证明:}$设两数$a,b$互质。 $G(a)G(b)$ $=\sum\limits_{d|a}F_1(d)F_2(a/d)*\sum\limits_{t|b}F_1(t)F_2(b/t)$ $=\sum\limits_{d|a}\sum\limits_{t|b}F_1(d)F_2(a/d)F_1(t)F_2(b/t)$ 把$\sum$合并(根据约数集合的合并),由于$a$与$b$互质,所以$t$与$d$互质。 (根据积性可以把$F_1(d)F_1(t)$化为$F_1(dt)$,$F_2$类似) $=\sum\limits_{dt|ab}F_1(dt)F_2(ab/dt)$ $=G(ab)$,得证. - 积性函数的逆也是积性函数 (初学者可以先跳过证明) 来介绍一下函数在狄利克雷卷积意义下的**逆**。 $\color{blue}\text{定义:}$满足$e=g*f$时,$g$和$f$互逆。 (类比同余逆元理解) 附:函数的逆可以通过某种方式构造出来:[构造方法](https://www.luogu.org/paste/64fn78k9)(~~然并卵~~) $\color{blue}\text{证明:}$ 考虑**数学归纳法**(跟构造方法有点像) 设$e=G*F$,且$F$是积性函数。 我们要证明对于任意的$(a,b)=1$的$a,b$,都满足$G(ab)=G(a)G(b)$ 因为$e=\sum\limits_{d|n}F(d)G(n/d)$ - 1) a或b为1 当$a=b=1$时,$e(1)=1=F(1)G(1)$ 由于积性,根据上文$F(1)=1$,得$G(1)=1$ 所以当$a$或$b=1$时,结论显然成立。 - 2) ab>1 我们考虑已证明了所有的$a'<a;\ b'<b$时,结论成立。 $G(ab)=\sum\limits_{d|ab}F(d)G(ab/d)-\sum\limits_{d|ab,d≠1}F(d)G(ab/d)$ 由$e=G*F$,得$\sum\limits_{d|ab}F(d)G(ab/d)=e(ab)$,由于$ab>1$所以$e(ab)=0$。 $=-\sum\limits_{d|ab,d≠1}F(d)G(ab/d)$ $=-\sum\limits_{i|a,j|b,ij≠1}F(ij)G(ab/ij)$ 根据所有的$a'<a;\ b'<b$时,积性成立得 $=-\sum\limits_{i|a,j|b,ij≠1}F(i)G(j)F(a/i)G(b/j)$ $=-\sum\limits_{i|a,j|b,ij≠1}F(i)G(a/i)F(j)G(b/j)$ 下面**拆分求和号**(乘法分配律),这一步有点难。 $=-\sum\limits_{i|a}F(i)G(a/i)\sum\limits_{j|b,ij≠1}F(j)G(b/j)$ 要求$ij≠1$,即排除$i=j=1$的情况。 $=F(1)F(1)G(a)G(b)-\sum\limits_{i|a}F(i)G(a/i)\sum\limits_{j|b}F(j)G(b/j)$ 由$e=G*F$,得$\sum\limits_{i|a}F(i)G(a/i)\sum\limits_{j|b}F(j)G(b/j)=e(a)e(b)=0$得 $=F(1)F(1)G(a)G(b)$ 由于积性,根据上文$F(1)=1$,得 $=G(a)G(b)$,得证. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ------------ # 2.莫反公式的推导: ——推导了$\mu$函数,莫比乌斯反演定理 有两个单变量函数 **F** 与 **f** 。 设函数 **F** 与 **f** 有如下关系： $F(n)=\sum\limits_{d|n}f(d)$ 理解了上述狄利克雷卷积的定义后,不难发现。 $F(n)=\sum\limits_{d|n}(1*f(d))$(~~废话~~) $F=I*f$ (**F函数是元函数和f函数的卷积**) 现在如果$f$函数易求,那我们可以按照上式算出$F$。 问题在于,如果即$F$函数易求,如何求出$f$? $F=I*f$,两边同时乘以$I^{-1}$得 $f=I^{-1}*F$ 我们只要想办法求出$I^{-1}$就好了。 大佬Möbius把$I^{-1}$命名为$\mu$ 问题在于这个函数里面是什么呢? **$\mu$是个积性函数**,因为积性函数的逆还是积性函数。 这里有个小技巧,研究一个积性函数,**先研究其在质数的幂时的表现**。 比如说$\mu(p^k)$(p是质数)。 **k=0时**,显然有$\mu(1)=1$ **k=1时**,由于$\sum\limits_{d|p}I(d)\mu(p/d)=e(p)=0$ 注意到p为素数,得到$I(p)\mu(1)+I(1)\mu(p)=e(p)=0$ 因为$\mu(1)=1$得$1+\mu(p)=0$,即$\large{\mu(p)=-1}$ **k>1时**,由于$\sum\limits_{d|p^k}I(d)\mu(p^k/d)=e(p^k)=0$ 注意到p为素数,得到$I(p^k)\mu(1)+I(p^{k-1})\mu(p)+...+I(1)\mu(p^k)=e(p^k)=0$ 所有的$I$都为1,得到$\mu(1)+\mu(p)+\mu(p^2)...+\mu(p^k)=0$ 代入$\mu(1)=1,\mu(p)=-1$得到$\mu(p^2)...+\mu(p^k)=0$ 考虑上式k=2的情况,得到$\mu(p^2)=0$ 考虑上式k=3的情况,得到$mu(p^2)+mu(p^3)=0$也就是$mu(p^3)=0$ ……,得到k=任意更大的数时$mu(p^k)=0$ 利用数学归纳法,证明了k>1时,$\mu(p^k)=0$。 大家缓口气哦,$\mu$函数的终极定义马上就证明出来了。 由于上文积性函数性质2: $\mu(n=p_1^{k_1}p_2^{k_2}...p_m^{k_m})=\mu(p_1^{k_1})\mu(p_2^{k_2})...\mu(p_m^{k_m})$ 因为k>1时,$\mu(p^k)=0$ 可以想象到当某一个$k>1$时,$\mu(n)=0$ 不然的话所有的k=1。 可以想象到$\mu(n=p_1p_2...p_m)=(-1)^{m}$ **mu** 函数的$\color{blue}\text{定义}$浮出水面。  现在来介绍莫比乌斯函数是怎么用来反演的。 - **反演公式:** - **嵌入式**莫比乌斯反演： 由$\mu*I=e$得$\sum\limits_{d|n}\mu(d)=[n=1]$ 注意到$[n|m][n/m=1]=[n=m]$ 则有$[n|m]\sum\limits_{d|(n/m)}\mu(d)=[n=m]$ 初学者可以只掌握这一种。 - **约数**的莫比乌斯反演： 若：$\large{F(n)=∑\limits_{d|n}f(d)}$ 则：$\large{f(n)=∑\limits_{d|n}μ(d)F(n/d)}$ 又作$f(n)=∑\limits_{d|n}μ(n/d)F(d)$(和上面那个式子等价) 根据$\mu=I^{-1}$有$f*I=F\rightarrow f=F*\mu$。 如果你们喜欢和式的话:[证明2](https://www.luogu.org/paste/8znlp82b) - **倍数**的莫比乌斯反演： 若：$\large{F(n)=∑\limits_{n|d}f(d)}$ 则：$\large{f(n)=∑\limits_{n|d}μ(d/n)F(d)}$ （这个比较特殊,并不是狄利克雷卷积的形式） 又作$F(n)=\sum\limits_{k}^∞f(kn)$与$f(n)=\sum\limits_{k}^∞\mu(k)F(kn)$ $\color{blue}\text{证明:}$ $∑\limits_{n|d}μ(n/d)F(d)$ 将$F(n)$的定义代入。 $=∑\limits_{n|d}μ(n/d)\sum\limits_{d|t}f(t)$ $=∑\limits_{k}^{∞}μ(k)\sum\limits_{nk|t}f(t)$ 第一个求和号对k没有限制,我们**交换求和号**,考虑枚举t,看有什么对应的k: $=∑\limits_{t}f(t)\sum\limits_{nk|t}\mu(k)=∑\limits_{t}f(t)\sum\limits_{k|(t/n),n|t}\mu(k)$ 根据嵌入式反演能得到$\sum\limits_{k|(t/n),n|t}\mu(k)=[t=n]$ $=∑\limits_{t}f(t)[t=n] =f(n)$,证毕。 -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ------------ # 3.知识储备: - **分解质因数**求法,单个mu(n) 直接按照定义,分解因数暴力求。 ```cpp 代码被和谐 //Time:O(sqrt(n)) ``` - **线性筛法**,mu(1~n) (正宗) 利用$\mu$函数的积性性质。 想深入学习线性筛法的看[这里](https://www.cnblogs.com/Paul-Guderian/p/7723031.html)。 ```cpp #include<iostream> #include<cstring> #define MaxNum 10000100 using namespace std; bool e[MaxNum]; int p[MaxNum],tn,mu[MaxNum],n; void Mobius() { e[1]=1;mu[1]=1; for (int i=2;i<=n;i++){ if (!e[i]){p[++tn]=i;mu[i]=-1;} for (int j=1;j<=tn;j++){ if (p[j]*i>n)break; mu[p[j]*i]=i%p[j]==0 ? 0 : -mu[i]; e[p[j]*i]=1; if (i%p[j]==0)break; } } } int main() { cin>>n; Mobius(); for(int i=1;i<=n;++i) printf("%d: %d\n",i,mu[i]); return 0; }//Time:O(n) ``` -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ------------ # 4.第一道题:整除分块 (除了特殊说明,除法均为整除) 讲了那么多,那么问题来了:我们问什么要学莫比乌斯反演?这有什么用呢? 来看一道**题目**。 让你求$\large{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m[gcd(i,j)=1]}$，也就是互质数对数。($m\leq n$) 大力两重循环+欧几里得$O(n^2logn)$? 悄悄告诉你,正解$O(\sqrt{n})$! $ANS=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m[(i,j)=1]$。 用**嵌入式反演**替换 : $[(i,j)=1]=\sum\limits_{d|(i,j)}\mu(d)$ - $\color{blue}\text{技巧:}$数对$(i,j)$满足$[d|gcd(i,j)]$的充要条件是$d|i$且$d|j$。 即$[d|(i,j)]=[d|i][d|j]$, 人话就是 : 即是$i$的约数又是$j$的约数的数是$i,j$的公约数。 则有$[(i,j)=1]=\sum\limits_{d|i,d|j}\mu(d)$,这比较重要。 $ANS=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m\sum\limits_{d|i,d|j}\mu(d)$ $\color{blue}\text{技巧:}$ 我们考虑**交换求和顺序**,分别查看每个变量的限制。 $d$最先枚举,考虑其范围,显然在$[1,n]$以内。 $i$必须要满足$d|i$,且在$[1,n]$以内。 $j$必须要满足$d|j$,且在$[1,n]$以内。 $ANS=\sum\limits_{d=1}^n\mu(d)\sum\limits_{d|i}^{n}\sum\limits_{d|j}^m1$ 观察后面的$\sum\limits_{d|i}^{n}\sum\limits_{d|j}^m1=(\sum\limits_{d|i}^{n}1)(\sum\limits_{d|j}^m1)$ 而$\sum\limits_{d|i}^{n}1$相当于$n$以内$d$的倍数的个数,显然为$\lfloor n/d\rfloor$ 就得到$ANS=\sum\limits_{d=1}^n\mu(d)\lfloor n/d\rfloor\lfloor m/d\rfloor$ 这样子就可以$O(n)$计算了。 $\color{blue}\text{技巧:}$怎么做到$O(\sqrt{n})$呢?需要一个叫做**整除分块**的技巧。 [整除分块入门小记](https://www.luogu.org/blog/command-block/zheng-chu-fen-kuai-ru-men-xiao-ji) 好的,下面我们默认你会整除分块了。 回顾上面的问题,我们已经变形到了$ANS=∑\limits_{d=1}^{min(n,m)}μ(d)\lfloor n/d\rfloor \lfloor m/d\rfloor$ 看到和式后面的$\lfloor n/d\rfloor \lfloor m/d\rfloor$,是可以整除分块的。 问题是还乘了个$\mu(d)$,根据套路弄个前缀和搞定。 (如果这句听不懂,把入门小记再看一遍) 即$\mu([l,r])$的和乘上$\lfloor n/d\rfloor \lfloor m/d\rfloor$。 Code: ```cpp #include<iostream> #define MaxNum 100100 using namespace std; int p[MaxNum/8],tn,mu[MaxNum],n,m; bool e[MaxNum]; long long calc(int n,int m) { long long ans=0; for (int l=1,r=0;l<=min(n,m);l=r+1){ r=min(n/(n/l),m/(m/l));// 分段 ans+=1ll*(mu[r]-mu[l-1])*(n/l)*(m/l); }return ans; } int main() { e[1]=1;mu[1]=1; for (int i=2;i<=MaxNum;i++){ if (!e[i]){p[++tn]=i;mu[i]=-1;} for (int j=1;j<=tn;j++){ if (p[j]*i>MaxNum)break; mu[p[j]*i]=i%p[j]==0 ? 0 : -mu[i]; e[p[j]*i]=1; if (i%p[j]==0)break; } }for (int i=2;i<=MaxNum;i++)mu[i]+=mu[i-1]; //筛法弄出mu前缀和,参看前文 cin>>n>>m; cout<<calc(n,m)<<endl; return 0; } ``` ~~后面你会看到,莫比乌斯反演不分块复杂度就是一堆垃圾。~~ ~~分块是肯定要分块的,这辈子都要分块的~~ 恭喜你,已经在莫比乌斯反演的路上迈出了第一步! 附送可以**利用**上述代码AC的练手题[Link1](https://www.luogu.org/problemnew/show/P3455)+[Link2](https://www.luogu.org/problemnew/show/P2158) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ------------ ## 5.技巧进阶:莫反常用结论以及练习 莫比乌斯反演是极具技巧性的。 主要的思维难度就建立在**反演**和**分块**两部分。 看题吧。 ### 第一题[P2568 GCD](https://www.luogu.org/problemnew/show/P2568) 求$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=prime]$ 在上一题中,我们解决了求$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^n[(i,j)=1]$的问题,而且我们已经能够做到$O(\sqrt{n})$求解了。 我们尝试求$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=d]$ - 注意到,$[(i,j)=d]$蕴含$d|i$且$d|j$. $=\sum\limits_{d|i}^n\sum\limits_{d|j}^n[(i,j)=d]$ - $\color{blue}\text{技巧:}$ 既然$i,j$都是$d$的倍数,我们不妨把$i,j$都除以$d$ 此时,后面原有的$i$需要还原成$id$,原有的$j$要还原成$jd$ $=\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{n/d}[(id,jd)=d]$ - $[(id,jd)=d]=[d(i,j)=d]=[(i,j)=1]$ $=\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{n/d}[(i,j)=1]$,又回到了我们熟悉的问题! 求解的复杂度是$O(\sqrt{n/d})$ 对于每个素数求解的复杂度是$O\Big(\sum\limits_{p\in Prime}^{n}{\sqrt{n/p}}\Big)$ $=\sqrt{n}\sum\limits_{p\in Prime}^{n}{\sqrt{1/p}}$ 将素数视为平均分布,可估计额$\frac{1}{\log n}\sum\limits_{p=1}^{n}\sqrt{1/p}$ 接下来需要一点微积分知识 : $\sum\limits_{p=1}^{n}\sqrt{1/p}=\sqrt{n}$ 总的复杂度就是$O(n/\log n)$ 对于不会计算复杂度的同学,可以暴力统计一下式子的值,看看能不能过就好了。 **Code:** ```cpp #include<iostream> #include<cstdio> #define MaxNum 10000010 using namespace std; long long p[MaxNum/10],tn,mu[MaxNum+50],anss,ttn,n,aaa; bool e[MaxNum+50]; void getmu() { e[1]=1;mu[1]=1; for (long long i=2;i<=MaxNum;i++){ if (!e[i])mu[p[++tn]=i]=-1; for (int j=1;j<=tn&&i*p[j]<MaxNum;j++){ e[i*p[j]]=1; mu[i*p[j]]=i%p[j]? -mu[i] : 0; if (!i%p[j])break; } } } //sum(1,N/n)sum(1,N/n)[gcd(i,j)==1] long long gg(int n){ long long ans=0; for (int l=1,r=0;l<=n;l=r+1){ r=n/(n/l); // 分段 ans+=1ll*(mu[r]-mu[l-1])*(n/l)*(n/l); }return ans; } int main() { getmu(); for (int i=2;i<=MaxNum;i++)mu[i]+=mu[i-1]; cin>>n; long long ans=0; for (int i=2;i<=n;i++) if(!e[i])ans+=gg(n/i); cout<<ans; return 0; } ``` [P2257 YY的GCD](https://www.luogu.org/problemnew/show/P2257) 貌似和上一题相同呢？发现$T<=10000$。 上一题的$O(n/\log n)$还要乘上数据组数,肯定是跑不过去的。 我们将上面的最终式子整理: $\sum\limits_{p∈Prime}^{n}f(p)=\sum\limits_{p∈Prime}^{n}∑\limits_{d=1}^{m/p}μ(d)\lfloor n/dp\rfloor\lfloor m/dp\rfloor$ $\color{blue}\text{技巧:}$ 现在又有个蛇皮操作叫**改变枚举变量** 说起$dp$,我就想起……开机……弘扬中华文化。 还是把$dp$换一下吧,就令$dp=k$**我们枚举k**。容易发现$dp≤min(n,m)$ 明显的,$d$和$p$都是k的约数,我们再枚举$p$,得到$d=k/p$。（把枚举k的和式放在最前面） $\sum\limits_{k=1}^{min(n,m)}∑\limits_{p∈prime,p|k}μ(k/p)\lfloor n/k\rfloor\lfloor m/k\rfloor$ 我们发现只有$μ(k/p)$一项和$p$有关,所以我们可以把$μ(k/p)$连着$∑\limits_{p∈prime,p|k}$一起放到最后面。 得到$\sum\limits_{k=1}^{min(n,m)}\lfloor n/k\rfloor\lfloor m/k\rfloor∑\limits_{p∈prime,p|k}μ(k/p)$ 前面的$\sum\limits_{k=1}^{min(n,m)}\lfloor n/k\rfloor\lfloor m/k\rfloor$就可以**整除分块**了。 至于后面的$∑\limits_{p∈prime,p|k}μ(k/p)$还是套路,维护一个有关于$k$的前缀和。 怎么弄出前缀和,就是考验数论~~口胡~~基本功的时候啦,这里也介绍一下。 设$g(k)=∑\limits_{p∈prime,p|k}μ(k/p)$ 先线筛出$\mu$,然后枚举$p$,对于 $p|k$ 的$k$将$g[k]+=\mu(k/p)$。(贡献模式,好好理解) 这样的话对于一个素数$p$,复杂度为$O(n/p)$ 复杂度和埃氏筛相同,为$O(n\log\log n)$ 每个询问$O(\sqrt{n})$,总的复杂度$O(t\sqrt{n}+n\log\log n)$ 亮出代码: ```cpp #include<algorithm> #include<cstdio> using namespace std; int t,n,m,tn,p[1000500],mu[10000500],g[10000500]; bool e[10000500]; void getmu() { e[1]=1;mu[1]=1; for (int i=2;i<=10000100;i++){ if (!e[i]){ p[++tn]=i; mu[i]=-1; }for (int j=1;j<=tn;j++){ if (1ll*i*p[j]>10000100)break; e[i*p[j]]=1; mu[i*p[j]]=i%p[j] ? -mu[i] : 0; if (!i%p[j])break; } }//线筛出mu } long long calc(int n,int m) { long long ans=0; int l=1,r; for (;l<=min(n,m);l=r+1){ r=min(n/(n/l),m/(m/l));//整除分块 ans+=1ll*(n/l)*(m/l)*(g[r]-g[l-1]); }return ans; } int main() { scanf("%d",&t); getmu(); for (int i=1;i<=tn;i++) for (int j=p[i];j<=10000100;j+=p[i]) g[j]+=mu[j/p[i]]; for (int i=2;i<=10000100;i++)g[i]+=g[i-1]; //预处理前缀和 while(t--){ scanf("%d%d",&n,&m); printf("%lld\n",calc(n,m)); }return 0;} ``` $\color{blue}\text{附加题:}$ [P5221 Product](https://www.luogu.org/problemnew/show/P5221) **&** [My Sol](https://www.luogu.org/blog/command-block/solution-p5221) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ------------ ## 6.探索新知:其他数论函数 想必经过上面的学习，大家对$\mu$已经有了一定的了解，运用反演定理也更熟练了些，那么我们一起向**数论函数**这个广阔的天地进发吧! $\color{blue}\text{定义:}$**常用数论函数表：** | 函数名称 | 符号 | 定义 | 积性 | 卷积 | -------: | -------: | -------: | -------: | -------: | | 恒等函数 \|| $I(n)$ \|| 永远等于1 \|| 完全积性函数 \|| | | 元函数 \|| $ϵ(n)$(也作$e(n)$) \|| 当n为1时,函数值为1,否则为0 \|| 完全积性函数 \|| | | 单位函数 \|| $id(n)$ \|| 函数值为n \|| 完全积性函数 \|| | | 幂函数 \|| $id^x(n)$ \|| 函数值为$n^x$ \|| 完全积性函数 \|| | | 莫比乌斯函数 \|| $\mu(n)$`\mu` \|| $\mu*I=e$ \|| 积性函数 \|| $\mu*I=e$ | | 欧拉函数\|| $\varphi(n)$`\varphi` \|| 小于等于n的数中,与n互质的数的个数 \|| 积性函数 \|| $\varphi*I=id$ | | 约数个数函数 \|| $d(n)$(也作$σ_0(n)$) \|| n的约数个数 \|| 积性函数 \|| $d=I*I$ | | 约数和函数 \|| $σ(n)$ \|| n的约数和 \|| 积性函数 \|| $σ=id*I$ | | | 除数函数 \|| $σ^k(n)$ \|| n的约数k次方和 \|| 积性函数 \|| $σ^k=id^k*I$ | ### 1) 欧拉函数 $\color{blue}\text{定义:}$欧拉函数,$\varphi(n)$,其值为“小于等于n的数中,与n互质的数的个数”。 这个函数是可以辅助解（理解）很多的数论题的,它的地位差不多和$\mu$一样重要。 而且，$\varphi$和$\mu$之间有某些神秘联系，这一点要等我们先讲完狄利克雷卷积的一些玩法先。 先讲解这个$\varphi$的**基本操作**: $\color{blue}\text{性质:}$首先$\varphi$是**积性函数**。 $\color{blue}\text{证明:}$因为$\varphi(n)=\sum\limits_{i=1}^n[(n,i)=1]$ 设$(n,m)=1$, 得$\varphi(n)\varphi(m)=\sum\limits_{i=1}^n[(n,i)=1]\sum\limits_{j=1}^m[(m,j)=1]$ 即$\sum\limits_{i=1}^n\sum\limits_{j=1}^m[(m,j)=1\ {\bf and}\ (n,i)=1]$ 由于互质,$[(m,j)=1\ {\bf and}\ (n,i)=1]$**等价于**$[(nm,im+jn)=1]$。 因为$\gcd\Big((im+jn)\bmod n,n\Big)=\gcd(im,n)=1$,且$\gcd\Big((im+jn)\bmod m,m\Big)=\gcd(jn,m)=1$ 我们还要证明所有的$(in+jm)\bmod {nm}$**恰好**组成$[1...nm]$的集合。 首先,这些二元组的大小为$nm$,和目标集合大小相同,我们只需要证明这些元素两两不同即可。 **前置芝士** : $ca=cb\pmod p$且$(c,p)=1$,则有$a=b$. (可见[同余系基本定理1](https://www.luogu.com.cn/blog/command-block/tong-yu-xi1)) - 采用反证法,假如有$am+bn=cm+dn\pmod {nm}$ 我们将两边对$m$取模得到$bn=dn\pmod {m}$,由引理得$b=d$,同理有$a=c$,矛盾。 那么$(in+jm)\bmod {nm}$的集合与$[1...nm]$的集合一一对应,且贡献模式相同。 于是上式等价于$\sum\limits_{i=1}^{nm}[(nm,i)=1]=\varphi(nm)$ 如何求积性函数的前n个值呢? **线性筛!** 对于线性筛,我们要解决$\varphi(prime^k)$类的函数值。(下面的$p$均为素数) $\color{blue}\text{性质:}$ $\varphi(p^k)=(p-1)p^{(k-1)}$ $\color{blue}\text{证明:}$ $\varphi(p)=p-1$，这是很明显的:小于$p$的数都与$p$互质。 很明显$p^k$以内的数与$p^k$互质的充要条件是:它们没有公因数$p$。 那么把所有含有因数$p$的数去掉,剩下$\dfrac{(p-1)*p^k}{p}=(p-1)p^{(k-1)}$个。 在实用中这个定理有另外一个形式: 如果$p|n$,则$\varphi(np)=\varphi(n)*p$ $\color{blue}\text{证明:}$设$n=p^k*m$,那么$\varphi(n)=\varphi(m)*\varphi(p^k)=\varphi(m)*(p-1)p^{(k-1)}$ 则$np=p^{(k+1)}*m$,那么$\varphi(np)=\varphi(m)*\varphi(p^{(k+1)})=\varphi(m)*(p-1)p^k$ 原命题明显成立。 **Code:** ```cpp bitset<MaxN> e; int p[MaxN/10],tn; long long ans,phi[MaxN]; void getphi() { phi[1]=1; for (int i=2;i<=n;i++){ if (!e[i]){ p[++tn]=i; phi[i]=i-1; }for (int j=1,t;j<=tn&&(t=i*p[j])<=n;j++){ e[t]=1; phi[t]=phi[i]*(i%p[j]?p[j]-1:p[j]); //此处注意 if (i%p[j]==0)break; } } } ``` - 代码里"此处注意": 如果$(i,p)=1$,则$\varphi(ip)=\varphi(i)*\varphi(p)=(p-1)\varphi(i)$ 如果$p|i$,根据上文的定理,$\varphi(ip)=\varphi(i)*p$ - **附:** 有些时候我们需要求出单个的$\varphi(n)$,如果按照定义大力求,至少得$O(n)$次$\gcd$。 我们把$n$分解得$p_1^{k_1}*p_2^{k_2}*...*p_m^{k_m}$ 那么$\varphi(n)=\varphi(p_1^{k_1})*\varphi(p_2^{k_2})*...*\varphi(p_m^{k_m})=\dfrac{(p_1-1)p_1^k}{p_1}*\dfrac{(p_2-1)p_2^k}{p_2}*...\dfrac{(p_m-1)p_m^k}{p_m}$ $=(p_1^kp_2^{k_2}...p_m^{k_m})*\left(\dfrac{p_1-1}{p_1}*\dfrac{p_2-1}{p_2}*...*\dfrac{p_m-1}{p_m}\right)=n\left(\dfrac{p_1-1}{p_1}*\dfrac{p_2-1}{p_2}*...*\dfrac{p_m-1}{p_m}\right)$ $\color{blue}\text{性质:}$ $\varphi(n=p_1^kp_2^{k_2}...p_m^{k_m})=n\left(\dfrac{p_1-1}{p_1}*\dfrac{p_2-1}{p_2}*...*\dfrac{p_m-1}{p_m}\right)$ 根据上式,把$n$质因数分解即可求出$\varphi(n)$,复杂度$O(\sqrt{n})$ **Code:** ```cpp int phi(int n) { int ans=n; for (int i=2;i*i<=n;i++) if (n%i==0){ ans=ans/i*(i-1); //根据上文式子计算 while(n%i==0)n/=i; } if (n>1)ans=ans/n*(n-1); //如果分解不尽,那么肯定还剩一个素数 return ans; } ``` 我们来看看$\varphi$的经典**应用**: [题目](https://www.luogu.org/problemnew/show/P2398) 相信你能直接想到一个莫比乌斯反演的做法: - 设$f(n)$是$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=1]$ 考虑枚举gcd那么答案是$\sum\limits_{d=1}^nd\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=d]$ 后面的$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=d]=\sum\limits_{i=1}^{(n/d)}\sum\limits_{j=1}^{(n/d)}[(i,j)=1]=f(n/d)$ 答案化为$\sum\limits_{d=1}^nd*f(n/d)$。 对$f(n)$反演,……即为$∑\limits_{d=1}^{n}μ(d)(n/d)^2$,用整除分块求一次$f$时间复杂度$O(\sqrt{n})$ 按$\sum\limits_{d=1}^nd*f(n/d)$计算即可$O(n\sqrt{n})$。 考虑对$f(n/d)$的$n/d$整除分块,即可$O(n)-O(n^{3/4})$(方法参照上文,证明需用积分)。 其实利用$\varphi$可以**很方便**地解决上述问题,复杂度是$O(n)-O(\sqrt{n})$。 设$f(n)$是$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=1]$ 我们知道$\varphi(n)$的定义是:小于等于n的数中,与n互质的数的个数。 我们把$\varphi(1)+\varphi(2)+...+\varphi(n)$加起来,则可以得到**每个数与自己更小的数互质的次数和**。 即$\sum\limits_{i=1}^n\sum\limits_{j=1}^i[(i,j)=1]=\sum\limits_{i=1}^n\varphi(i)$ 现在，每个数只能统计比自己小的互质产生贡献，也就是，只统计了数对$(x,y)$中$x>=y$的部分。 我们考虑$(x,y)$中$x<=y$的部分贡献,显然和上式相同。 （想像一个邻接矩阵） 乘以$2$就好了，但是由于$(1,1)=1$会多算一次,所以答案减1。 $\color{blue}\text{技巧:}$得到$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=1]=2\left(\sum\limits_{i=1}^n\varphi(i)\right)-1$ 我们设$S(n)=\sum\limits_{i=1}^n\varphi(i)$(前缀和),上式变为$f(n)=2*s(n)-1$ 答案变为$\sum\limits_{d=1}^nd*f(n/d)=\sum\limits_{d=1}^nd*(2*S(n/d)-1)$已经可以做到$O(n)$了，再整除分快一次就可以$O(\sqrt{n})$了。 然后使用线性筛就得到$O(n)-O(\sqrt{n})$的算法了。 **Code:** ```cpp #include<cstdio> #include<bitset> #define MaxN 10000500 using namespace std; int n; bitset<MaxN> e; int p[MaxN/10],tn; long long ans,phi[MaxN]; void getphi() { phi[1]=1; for (int i=2;i<=n;i++){ if (!e[i]){ p[++tn]=i; phi[i]=i-1; }for (int j=1,t;j<=tn&&(t=i*p[j])<=n;j++){ e[t]=1; phi[t]=phi[i]*(i%p[j]?p[j]-1:p[j]); if (i%p[j]==0)break; } } } int main() { scanf("%d",&n); getphi(); for (int i=1;i<=n;i++)phi[i]+=phi[i-1]; for (int i=1;i<=n;i++)ans+=(phi[n/i]*2-1)*i; printf("%lld",ans); } ``` 这个解法相对莫比乌斯反演有什么好处呢? **代码短啊!** 如果多组询问的话,就可以使用数论分块$O(\sqrt{n})$回答啦。 重申经典结论:$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=1]=\left(\sum\limits_{i=1}^n\varphi(i)*2\right)-1$ 既然欧拉函数这么好用,为啥还要反演呢? 求$\sum\limits_{i=1}^n\sum\limits_{j=1}^m(i,j)$? 欧拉函数就没法直接按照定义做了。 这么说太过于人类智慧了,下面,我们考虑使用狄利克雷卷积来系统分析。 ### 2)一些狄利克雷卷积结论: - $id=I*\varphi$ 即$\sum\limits_{d|n}\varphi(d)=n$ 这个东西是比较重要的,相应地,证明也很长。 $\color{blue}\text{证明:}$设$id*\varphi=F$ 我们知道$F$是个积性函数,那么我们只要证明所有的$F(prime^k)=prime^k$成立。 然后根据积性和唯一分解定理,把结论扩展到全体正整数。 $\sum\limits_{d|p^k}\varphi(d)=\varphi(1)+\varphi(p)+\varphi(p^2)+...+\varphi(p^k)$ 根据$\varphi(p^k)=(p-1)p^{(k-1)}$,$\varphi(1)=1$ $=1+(p-1)+(p-1)p+(p-1)p^2...+(p-1)p^{(k-1)}$ $=1+(p-1)(1+p+p^2+...p^{(k-1)})$ $=1+(p-1)\dfrac{p^k-1}{p-1}=p^k$ 证毕。 根据$I^{-1}=\mu$,可得$id=I*\varphi$等价于$\mu*id=\varphi$ 即$\sum\limits_{d|n}\mu(d)(n/d)=\varphi(n)$ 这个结论极其有用,比如说我们求$\sum\limits_{i=1}^n\sum\limits_{j=1}^m(i,j)$ 利用莫比乌斯反演,变形为$\sum\limits_{d=1}^nd*∑\limits_{t=1}^{n/d}μ(t)\lfloor n/dt\rfloor\lfloor m/dt\rfloor$ 设$p=dt$,上式即为 $=\sum\limits_{d=1}^nd*∑\limits_{d|p}^{n}μ(p/d)\lfloor n/p\rfloor\lfloor m/p\rfloor$ 可以交换求和号,得到 $=∑\limits_{p=1}^{n}\sum\limits_{d|p}d*μ(p/d)\lfloor n/p\rfloor\lfloor m/p\rfloor$ 发现中间的$\sum\limits_{d|p}d*μ(p/d)$就是$\mu*id$所以等于$\varphi(p)$ $=∑\limits_{p=1}^{n}\varphi(p)\lfloor n/p\rfloor\lfloor m/p\rfloor$ (这个式子是可以整除分块的) 这样就可以解决上文留下的问题了。 ### 3)除数函数相关 - $d=I*I$ ; $\color{blue}\text{证明:}$ $d(n)=\sum\limits_{d|n}1=\sum\limits_{d|n}I(d)I(n/d)=(I*I)(n)$ - $σ=id*I$ $\color{blue}\text{证明:}$ $d(n)=\sum\limits_{d|n}d=\sum\limits_{d|n}id(d)I(n/d)=(id*I)(n)$ 把$n$分解得到$p_1^{k_1}*p_2^{k_2}*...*p_m^{k_m}$ $d(n)=(k_1+1)(k_2+1)...(k_m+1)$ $\color{blue}\text{证明:}$对于每个素因子可以选0~k个,乘法原理。 $σ(n)=(1+p_1+p_1^2+...+p_1^{k_1})(1+p_2+p_2^2+...+p_2^{k_2})...(1+p_m+p_m^2+...+p_m^{k_m})$ $=(\dfrac{p_1^{(k_1+1)}-1}{p_1-1})(\dfrac{p_2^{(k_2+1)}-1}{p_2-1})...(\dfrac{p_m^{(k_m+1)}-1}{p_m-1})$ $\color{blue}\text{证明:}$对于每个素因子可以选0~k个,拆完括号后刚好得到所有约数。 另外:$\sum\limits_{i=1}^nd(n)=\sum\limits_{i=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor$ $\color{blue}\text{证明:}$考虑$i$在1~n中被作为约数的次数,得$\left\lfloor\dfrac{n}{i}\right\rfloor$次。 [一道题目](https://www.luogu.org/problemnew/show/P3935) ### 4)一些(跳跃性)结论 在做某些毒瘤题的时候有奇效。 - 莫比乌斯函数$\mu(n)$ 有$\mu(ij)=\mu(i)\mu(j)[i\perp j]$ 这个容易,假如$(i,j)$大于1,那么一定会导致出现平方因子,式子的值为0. 否则按照积性分解即可。 - 除数函数$d(n)$ 有$d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[x\perp y]$ $\color{blue}\text{证明:}$ ~~比较难,只会从右边推到左边。~~ 把$i$分解得到$p_1^{k_1}*p_2^{k_2}*...*p_m^{k_m}$,$j$分解得到$p_1^{k_1'}*p_2^{k_2'}*...*p_m^{k_m'}$ $d(ij)=(k_1+k_1'+1)(k_2+k_2'+1)...(k_m+k_m'+1)$ 显然,每个质因子是独立的,我们考虑$i=p^a;j=p^b$的情况。 $\sum\limits_{x|i}\sum\limits_{y|j}[x\perp y]=\sum\limits_{x'=0}^a\sum\limits_{y'=0}^b[x',y'\text{不同时为正}]$ 大眼观察可得只有 $x'$取$0...a$,且$y'$取0这$a+1$个, $y'$取$0...b$,且$x'$取0这$b+1$个,减去重复算的$(0,0)$,正好是$(a+b+1)$,符合要求。 - 欧拉函数$\varphi(n)$ 有$\varphi(ij)=\dfrac{\varphi(i)\varphi(j)(i,j)}{\varphi((i,j))}$ $\color{blue}\text{证明:}$ 默认$p$指质数。 $\varphi(ij)=ij\prod\limits_{p|ij}\dfrac{p-1}{p}$ 考虑到$[p|ij]=[p|i\ or\ p|j]=[p|i]+[p|j]-[p|(i,j)]$ $=ij\left(\dfrac{\prod\limits_{p|i}\dfrac{p-1}{p}\prod\limits_{p|j}\dfrac{p-1}{p}}{\prod\limits_{p|(i,j)}\dfrac{p-1}{p}}\right)$ $=\dfrac{i\prod\limits_{p|i}\dfrac{p-1}{p}j\prod\limits_{p|j}\dfrac{p-1}{p}(i,j)}{(i,j)\prod\limits_{p|(i,j)}\dfrac{p-1}{p}}$ $=\dfrac{\varphi(i)\varphi(j)(i,j)}{\varphi((i,j))}$