数论初级魔法大赏(连载中)

最近在准备关于莫比乌斯反演的课件,准备把例题简要整理下来,那就开始吧

1.bzoj 2190 [SDOI2008]仪仗队

求\(2+\sum_{x=1}^{n-1}\sum_{y=1}^{n-1}[gcd(x,y)==1](n\le 40000)\)

最简单的做法,线性筛预处理出欧拉函数的前缀和,时间复杂度\(O(n)\)。

2.bzoj 2818 Gcd

求\(\sum_{p}\sum_{x=1}^{n}\sum_{y=1}^{n}[gcd(x,y)==p] (n\le 10^7)\)

其实就是\(\sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{n}{p}\rfloor}[gcd(x,y)==1]\),枚举所有质数后就是和上一道题一样做法了,双倍经验。

3.bzoj 2705 [SDOI2012]Longge的问题

求\(\sum_{i=1}^{n}gcd(i,n), n\le 2^{32}\)

变形一下,枚举每种gcd的值,即

\(\sum_{i=1}^{n}gcd(i,n)\)

\(=\sum_{d\mid n}d \sum_{x=1}^{\frac{n}{d}}[gcd(x,\frac{n}{d})==1]\)

\(=\sum_{d\mid n}d\varphi(\frac{n}{d})\)

那么根号枚举约数,单点求欧拉函数就做完了。

时间复杂度?是个经典的东西\(O(\sum_{i=1}^{\sqrt{n}}\sqrt{i}+\sqrt{\frac{n}{i}})=O(n^{\frac{3}{4}})\)

4.bzoj 2440 [中山市选2011]完全平方数

求第\(k(k\le 10^9)\)个不含完全平方数因子的正整数

二分答案,转为求前\(n\)个数中有多少数不含完全平方因子。容斥一下,总数减去是4(2的平方)的倍数的,减去9的倍数,16的倍数不用管,前面减过了,再减去25的倍数,加上36的倍数,因为前面多减了一次…那这样就发现了容斥系数就是莫比乌斯函数。时间复杂度\(O(\sqrt{n}\log{n})\)

5.luogu P2257 YY的GCD(bzoj 2820)

求\(\sum_{p}\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)==p] (n\le 10^7)\),\(T(\le 10000)\)组询问

bzoj 2818的加强版,把其中一个n换成了m,这样就不能用欧拉函数了,推导一下:

下述的\(p\)表示质数

\(\sum_{p}\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)==p]\)

\(=\sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor}[gcd(x,y)==1]\)

\(=\sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor}\sum_{d\mid gcd(x,y)}\mu(d)\)

\(=\sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor}\sum_{d\mid x \land d\mid y}\mu(d)\)

\(=\sum_{p}\sum_{d=1}^{\lfloor \frac{min(n,m)}{p}\rfloor}\mu(d)\lfloor \frac{n}{pd}\rfloor\lfloor \frac{m}{pd}\rfloor\)

\(=\sum_{k=1}^{min(n,m)}\sum_{p,p\mid k}\mu(\frac{k}{p})\lfloor \frac{n}{k}\rfloor\lfloor \frac{m}{k}\rfloor\)

\(=\sum_{k=1}^{min(n,m)}f(k)\lfloor \frac{n}{k}\rfloor\lfloor \frac{m}{k}\rfloor\)

其中第三行莫比乌斯反演,第五行交换求和,第六行令\(k=pd\),转而枚举\(k\),化简到最后用筛法预处理出所有\(f\)的值即可,这里应该可以用线性筛,不过懒得推导的话也可以枚举所有质数再枚举它的倍数这样求,那么时间复杂度就和埃氏筛一样了,之后每次求一组询问就是经典的数论分块了。时间复杂度\(O(n\log{\log{n}}+T\sqrt{n})\)。

6.spoj LCMSUM

求\(\sum_{i=1}^{n}lcm(i,n), n\le 10^{6}\),\(T(\le 300000)\)组询问。

\(\sum_{i=1}^{n}lcm(i,n)\)

\(=\sum_{i=1}^{n}\frac{i\times n}{gcd(i,n)}\)

\(=\frac{1}{2}\sum_{i=1}^{n-1}\frac{n^{2}}{gcd(i,n)}+n\)

\(=\frac{1}{2}\sum_{d\mid n,d\ne n}\frac{n^2}{d}\sum_{k=1}^{\lfloor \frac{n}{d}\rfloor}[gcd(k,\frac{n}{d})==1]+n\)

\(=\frac{1}{2}n\sum_{d\mid n,d\ne n}\frac{n}{d}\varphi(\frac{n}{d})+n\)

\(=\frac{1}{2}n\sum_{d\mid n,d\ne 1}d\varphi(d)+n\)

\(=\frac{1}{2}nf(n)+n\)

这样线性筛预处理完,\(O(n\log{n})\)的求出函数值\(f\),每次回答\(O(1)\)即可。

7.bzoj 2154 Crash的数字表格

求\(\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j),n,m\le 10^7\)

\(\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)\)

\(=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{gcd(i,j)}\)

\(=\sum_{d=1}^{min(n,m)}\sum_{x=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{d}\rfloor}dxy[gcd(x,y)==1]\)

\(=\sum_{d=1}^{min(n,m)}d\sum_{x=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{d}\rfloor}xy\sum_{k\mid x \land k\mid y}\mu(k)\)

\(=\sum_{d=1}^{min(n,m)}d\sum_{k=1}^{\lfloor \frac{m}{d}\rfloor}\mu(k)\sum_{x=1}^{\lfloor \frac{n}{dk}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{dk}\rfloor}k^{2}xy\)

\(=\sum_{T=1}^{min(n,m)}\sum_{k\mid T}kT\mu(k)g(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)\)

\(=\sum_{T=1}^{min(n,m)}Tg(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)\sum_{k\mid T}k\mu(k)\)

\(=\sum_{T=1}^{min(n,m)}Tg(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)f(T)\)

 

其中\(g(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}ij=\frac{n(n+1)}{2}\frac{m(m+1)}{2}\)

一开始头铁,\(O(n\log{n})\)求的\(f(T)\)的值,超时无疑,然后学习了用线性筛求积性函数\(f(T)=\sum_{k\mid T}k\mu(k)\)的思路。

线性筛过程分两种情况讨论

1.\(prime_j\)整除\(i\),那么枚举\(i*prime_j\)的约数\(k\)时,如果关于\(prime_j\)的指数大于等于2的话莫比乌斯函数为零,对答案没有贡献,所以此时\(f(i*prime_j)=f(i)\)。

2.\(prime_j\)不整除\(i\),那么再分枚举的约数\(k\)是否含有\(prime_j\),不含有的部分就是\(f(i)\),含\(prime_j\)的话,整体乘上这么多,并且莫比乌斯函数要变号,是\(-f(i)prime_j\)。综上,此时\(f(i*prime_j)=(1-prime_j)f(i)\)。

这样这道题就做完了,时间复杂度\(O(n)\)。

8.bzoj 3994 [SDOI2015]约数个数和

求\(\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij), n,m\le 50000\),\(T(\le 50000)\)组询问,其中\(d\)是约数个数函数。

这个题一开始卡在一个结论上了,首先要知道\(d(ij)=\sum_{x\mid i}\sum_{y\mid j}[gcd(x,y)==1]\),这个结论不好想,但可以用分解质因数的形式结合约数个数定理推出来,那解决了第一步,后面的就简单了。

\(\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)\)

\(=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}[gcd(x,y)==1]\)

\(=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}\sum_{k\mid  gcd(x,y)}\mu(k)\)

\(=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}\sum_{k\mid x \land k\mid y}\mu(k)\)

\(=\sum_{k=1}^{min(n,m)}\mu(k)\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{k}\rfloor}\lfloor\frac{n}{xk}\rfloor\lfloor\frac{m}{yk}\rfloor\)

\(=\sum_{k=1}^{min(n,m)}\mu(k)\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\lfloor\frac{n}{xk}\rfloor f(\lfloor\frac{m}{k}\rfloor)\)

\(=\sum_{k=1}^{min(n,m)}\mu(k)f(\lfloor\frac{n}{k}\rfloor) f(\lfloor\frac{m}{k}\rfloor)\)

至此又可以数论分块搞定单组询问了,时间复杂度\(O(T\sqrt{n})\)。

9.bzoj 4659 lcm

化简下题意就是求\(\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)[\mu^2(gcd(i,j))==1],n,m\le 4000000\),对\(2^{30}\)取模,\(T(\le 2000)\)组询问。发现就是在第七题的基础上加了个多组询问,且只统计\(\mu^2(gcd(i,j))==1\)的。

那么前面的推导都是一样的,最后化简到

原式\(=\sum_{T=1}^{min(n,m)}g(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)T\sum_{k\mid T}k\mu(k)\mu^2(\frac{T}{k})\)

头铁依然会TLE,还是先观察一下

\(f(T)=\sum_{k\mid T}k\mu(k)\mu^2(\frac{T}{k})\)是积性函数

且当\(T\)分解质因数后的指数中有大于2的情况的话,显然此时\(f(T)=0\),并且易知\(f(p)=1-p,f(p^2)=-p\),这样又可以线性筛搞一搞了,然后预处理出\(if(i)\)的前缀和。

10.bzoj 4816 [Sdoi2017]数字表格

求\(\prod_{i=1}^{n}\prod_{j=1}^{m}f(gcd(i,j)),n,m\le 10^6\),其中\(f\)为斐波那契数列,结果模\(10^9+7\),\(T(\le 1000)\)组询问。

\(\prod_{i=1}^{n}\prod_{j=1}^{m}f(gcd(i,j))\)

\(=\prod_{d=1}^{min(n,m)}f(d)^{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)==1]}\)

\(=\prod_{d=1}^{min(n,m)}f(d)^{\sum_{k=1}^{min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\mu(k)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor}\)

这样指数部分是关于\(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor\)的函数,可以分块,又因为外层是枚举的\(d\),所以分块套分块即可!时间复杂度\(O(T(n^{\frac{3}{4}}+\sqrt{n}\log{n}))\),前一部分来源分析同第三题