莫比乌斯反演

前言

这篇文章会很长!我会先从容斥原理开始讲,然后是线性筛,积性函数,欧拉函数,莫比乌斯反演,莫比乌斯函数,以及一些习题。这个问题很早就在《组合数学》上看到过,但是完全看不懂。GDOI2016的时候感觉基本上所有其他选手都会,讲得神乎其神,意识到自己与他人的差距,而且这个差距必须补上来。这几天我花了大量的时间,参考网上的资料以及教材,归纳出了一个自己比较容易理解的方法,做了一个总结。希望在写完这篇总结之后,能够在数论方面有更深刻的理解。

容斥原理

小学奥数题

先用一个小学奥数的问题来引入:

有一根30cm长的木棍,从头开始,先每隔2cm切一刀,再每隔3cm切一刀,再每隔5cm切一刀,问最终剩下多少段木棍?

如果只考虑每隔2cm切一刀,就是说分成很多个2cm小段,那么一共会切出30/2=15段来。3cm和5cm也类似。但是在切的时候,有一些地方已经切过了,所以再切一次不会创造出新的小段来。为了解决这个问题,考虑一种等价的形式:每一次有效的切割对应一段(末尾也要算)。我们画一个维恩图,可以看到每6cm就会2cm和3cm重复切一次,每10cm就2cm和5cm重复切一次,每15cm就有3cm和5cm重复切一次,最后每30cm就是2cm、3cm、5cm重复切的地方。

要统计有效的切割有多少,只需要求这三个集合的并集就可以了。这道题中很明显可以发现答案:

ans=302+303+30530630103015+3030ans=\frac {30} 2+\frac {30} 3+\frac {30} 5-\frac {30} {6}-\frac {30} {10}-\frac {30} {15}+\frac {30} {30}

最后要加上一个30/30是因为中间那个小的勒洛三角形被加了三次然后减了三次,但是它还要计数,所以又要加一次。

一般的容斥原理

我们现在考虑一般的情况。设A|A|为集合A的元素个数。我们的容斥原理本质上就是要求A1A2A3...Ak\left |A_ 1\cup A_ 2 \cup A_ 3 \cup ... \cup A_ k\right |,我们可以简记为:Ak\left |\bigcup A_ k\right |

那么这个的值应该这样计算:

Ak\left | \bigcup A_ k \right |

=Akk1k2Ak1Ak2+k1k2k3Ak1Ak2Ak3...+(1)nAk=\sum \left | A_ k \right | - \sum_ {k_ 1\neq k_ 2}\left | A_ {k_ 1}\cap A_ {k_ 2} \right | + \sum_ {k_ 1\neq k_ 2 \neq k_ 3}\left | A_ {k_ 1}\cap A_ {k_ 2}\cap A_ {k_ 3}\right | -...+(-1)^n \left | \bigcap A_ k \right |

这个的正确性可以这样证明:对于每一个元素,对左边的贡献为1;对右边的贡献,假设它存在于k个集合中,对应到上式的RHS,为

CreditCredit

=Ck1Ck2+Ck3...+(1)k1Ckk=C_k^1-C_k^2+C_k^3-...+(-1)^{k-1}C_k^k

=(i=0kCki1ki×(1)iCk0)=-(\sum_{i=0}^k C_k^i \cdot 1^{k-i}\times (-1)^i-C_k^0)

=(11)k+1=-(1-1)^k+1

=1=1

第一个等号右边是怎么得到的?先设这个元素为X吧,既然它在k个集合中存在,那么每一项就对应从k个集合中选i个集合出来的选法,每一个选法都会贡献1的值。第二个等式合并了一下列出来的式子,便于观察,发现可以使用二项式定理,得到第三个式子,然后……就非常简单了。每一个元素对右边的式子的贡献也为1.这便是容斥原理的形式化证明。

线性筛

要检验一个数n是否为素数,只要检查小于n\sqrt{n}的数中是否有能整除n的就可以了;如果要求素数表,我们一般采取的策略是筛(dǎ)法(biǎo),即假如一个数是素数,那么把这个素数的倍数全部划掉,再继续找下一个素数。网上好像说这种传统方法的时间复杂度是O(nloglogn)O(n\log\log n)的。

既然叫线性筛,那么时间复杂度必须得是线性的才行嘛……线性筛法又名欧拉筛法,它对基本的筛法做了一个小改进。

我们从定义上知道一个合数有不同的素数因数,所以它可能会被不同的素数筛掉,这就造成了重复和浪费。线性筛法通过一句小优化,使得每个数只会是素数,或者会被它最小的素因数筛掉。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#define N 1000010
using namespace std;
bool np[N];
int prime[N],ptop=0;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	np[0]=np[1]=true;
	for(int i=2;i<=1000000;i++){
		if(!np[i]){
			prime[ptop++]=i;
		}
		for(int j=0;j<ptop&&prime[j]*i<=1000000;j++){
			np[i*prime[j]]=true;
			if(i%prime[j]==0){
				break;
			}
		}
	}
	cout<<prime[n-1];
}

这里的np如果为true,就说明它不是素数。prime数组储存素数表。i枚举的是素数的倍数,同时也可以检查i是否为素数。prime[j]枚举素数。

有一行神奇的代码:if(i%prime[j]==0)。请记住,在线性筛法中,能筛掉一个数的唯一一种可能就是它的最小素因数。假设有primejiprime_ j|i,令t=iprimejt=\frac {i}{prime_ j},那么对于任意primep>primejprime_ p>prime_ j,我们如果想要筛掉primepi=primeptprimejprime_ p\cdot i=prime_ p\cdot t\cdot prime_ j,这时候就不应该用primepprime_ p来筛掉iprimepi\cdot prime_ p,而应该等i=primepti=prime_ p\cdot t的时候再使用primejprime_ j来筛掉iprimepi\cdot prime_ p,因为primejprime_ j才是iprimepi\cdot prime_ p的最小素因数。这样一来,当i%prime[j]==0的时候,就应当终止循环,后面的不必再算。

时间复杂度的证明十分简单,因为每一个元素都只会被筛掉一次,if语句判断对于每一个数耗的时间都一样,所以时间复杂度为线性的O(n)O(n)

关于线性筛的比较权威的论文还是建议参考贾志鹏的《线性筛与积性函数》,虽然它讲得简略,有点难看懂。

积性函数

概念

高中生应该多多少少做过一些抽象函数的题,但是那些题都比较单调,没有什么变化。积性函数对于gcd(a,b)=1gcd(a,b)=1f(ab)=f(a)f(b)f(a\cdot b)=f(a)\cdot f(b);特别地,如果对于所有正整数有f(ab)=f(a)f(b)f(a\cdot b)=f(a)\cdot f(b),那么f(x)还被称为完全积性函数。

积性函数可以很好地融合到线性筛中

还是使用上面的代码,我们加几句话进去:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#define N 1000010
using namespace std;
bool np[N];
int prime[N],ptop=0;
//Here
int f[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	np[0]=np[1]=true;
	for(int i=2;i<=1000000;i++){
		if(!np[i]){
			prime[ptop++]=i;
			//Here
			f[i]=1;
		}
		for(int j=0;j<ptop&&prime[j]*i<=1000000;j++){
			np[i*prime[j]]=true;
			if(i%prime[j]==0){
				//Here
				//some operations
				break;
			}else{
				//Here
				f[i*prime[j]]=f[i]*f[prime[j]];
			}
		}
	}
	cout<<prime[n-1];
}

代码中几处加了注释的地方相当于一个线性求积性函数的模板。下面解释一下那些地方都应该干些什么。

  1. 这里当然是开一个数组储存一下函数值啊。一般这种积性函数都需要预处理出来,不然在线计算的时间复杂度一定会很高。
  2. 对一个素数的函数值的初始化。也会因函数的定义不同而异
  3. 还是函数的一些操作。不过这里的iprime[j]不是互质的,而是倍数关系。
  4. 这里满足积性关系。因为i不是prime[j]的倍数,而且prime[j]是一个素数,所以iprime[j]一定会互质,那么我们就可以利用积性函数的性质来求出f[i*prime[j]]的值。

那么我们接下来就举一个例子看看吧。

欧拉函数

定义

欧拉函数φ(x)\varphi(x)为小于等于x且与x互质的正整数个数。

求法

枚举

枚举是最简单的了。人、计算机都可以使用。

通式

要想快一些,我们首先需要将其分解质因数。会得到欧拉函数的通式:

φ(x)=x(11p1)(11p2)(11p3)...(11pn)\varphi(x)=x(1-\frac 1 {p_1})(1-\frac 1 {p_2})(1-\frac 1 {p_3})...(1-\frac 1 {p_n})

其中p1,p2...pnp_ 1,p_ 2...p_ nxx的所有质因数,xx是不为0的整数。

说实话,这个我也不是很会证明,感性地说,先筛去p1p_ 1的所有倍数,剩下的素因数的倍数还是平均分布的,所以可以直接再筛去p2p_ 2p3p_ 3等等的倍数。可以参考百度百科,上面有证明。

组合论

使用先前讲到的容斥原理的思想。还是先分解质因数,p1p_ 1的倍数有np1\left \lfloor \frac{n}{p_ 1} \right \rfloor个,p2p_ 2的倍数有np2\left \lfloor \frac{n}{p_ 2} \right \rfloor个,……。但是他们的倍数有重复的数,它们不能重复计数,所以又要减去np1p2\left \lfloor \frac{n}{p_1p_ 2} \right \rfloor……然后因为减多了,又要加上……

这部分可以自己对照上面切割木棍的问题来看,很容易想明白。到这里,事实上已经和莫比乌斯反演非常非常近了。

计算机批量求

计算机批量地求欧拉函数需要一些性质。

  1. 对于任意素数pp,有φ(p)=p1\varphi(p)=p-1。非常容易证明,由定义可知,除了它自己,其他小于它的数都与它互质,而一共有p1p-1个正整数比它小。
  2. 欧拉函数是积性函数!

这样就可以上程序了。

#include <iostream>
#include <cstdio>
#include <cstring>
#define N 10000010
using namespace std;
int phi[N],prime[N],ptop=0;
bool np[N];
int main(){
	memset(np,0,sizeof(np));
	int n;
	scanf("%d",&n);
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!np[i]){
			prime[ptop++]=i;
			phi[i]=i-1;//1
		}
		for(int j=0;j<=n&&i*prime[j]<=n;j++){
			np[i*prime[j]]=true;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];//2
				break;
			}else{
				phi[i*prime[j]]=phi[i]*phi[prime[j]];//3
			}
		}
	}
	printf("%d",phi[n]);
}

说明:

  1. i为素数,所以应用性质1直接得出。
  2. 通式:φ(x)=x(11p1)(11p2)(11p3)(11p4)...(11pn)\varphi(x)=x(1-\frac{1}{p_ 1})(1-\frac{1}{p_ 2})(1-\frac{1}{p_ 3})(1-\frac{1}{p_ 4})...(1-\frac{1}{p_ n})i%prime[j]==0说明i中已经有了prime[j]这个素因子,不需要再添加,得φ(iprimej)=iprimej(11p2)(11p3)(11p4)...(11pn)=φ(i)primej\varphi(i*prime_ j)=i\cdot prime_ j\cdot(1-\frac{1}{p_ 2})(1-\frac{1}{p_ 3})(1-\frac{1}{p_ 4})...(1-\frac{1}{p_ n})=\varphi(i)*prime_ j
  3. 在筛法模板里面说过,既然prime[j]不整除i,那么iprime[j]一定是互质的,应用积性性质即可。

莫比乌斯反演

f(n)=dng(d)f(n)=\sum_{d|n} g(d)

考虑这样一个函数。dnd|n的意思是nn能够被dd整除。假如说我们已经知道了f(n)f(n)是什么样的,有没有可能倒回去得到g(n)g(n)是什么样的呢?

g(36)g(36)举个例子。

|ff|g(1)g(1)|g(2)g(2)|g(3)g(3)|g(4)g(4)|g(6)g(6)|g(9)g(9)|g(12)g(12)|g(18)g(18)|g(36)g(36)|
|==|==|==|==|==|==|==|==|==|==|
|+f(36)+f(36)|11|11|11|11|11|11|11|11|11|
|f(18)-f(18)|1-1|1-1|1-1||1-1|1-1||1-1||
|f(12)-f(12)|1-1|1-1|1-1|1-1|1-1||1-1|||
|+f(6)+f(6)|11|11|11||11|||||
|总计|00|00|00|00|00|00|00|00|11|

所以g(36)=f(36)f(18)f(12)+f(6)g(36)=f(36)-f(18)-f(12)+f(6)

为了找到更多普遍规律,我们再列举一串反演之后得到的g(x)的值。

  • g(1)=f(1)g(1)=f(1)
  • g(2)=f(2)f(1)g(2)=f(2)-f(1)
  • g(3)=f(3)f(1)g(3)=f(3)-f(1)
  • g(4)=f(4)f(2)g(4)=f(4)-f(2)
  • g(5)=f(5)f(1)g(5)=f(5)-f(1)
  • g(6)=f(6)f(3)f(2)+f(1)g(6)=f(6)-f(3)-f(2)+f(1)
  • g(7)=f(7)f(1)g(7)=f(7)-f(1)
  • g(8)=f(8)f(4)g(8)=f(8)-f(4)
  • g(9)=f(9)f(3)g(9)=f(9)-f(3)
  • g(10)=f(10)f(5)f(2)+f(1)g(10)=f(10)-f(5)-f(2)+f(1)
  • g(11)=f(11)f(1)g(11)=f(11)-f(1)
  • g(12)=f(12)f(6)f(4)+f(2)g(12)=f(12)-f(6)-f(4)+f(2)

再变换一下,

  • g(1)=f(11)g(1)=f(\frac 1 1)
  • g(2)=f(21)f(22)g(2)=f(\frac 2 1)-f(\frac 2 2)
  • g(3)=f(31)f(33)g(3)=f(\frac 3 1)-f(\frac 3 3)
  • g(4)=f(41)f(42)g(4)=f(\frac 4 1)-f(\frac 4 2)
  • g(5)=f(51)f(55)g(5)=f(\frac 5 1)-f(\frac 5 5)
  • g(6)=f(61)f(62)f(63)+f(66)g(6)=f(\frac 6 1)-f(\frac 6 2)-f(\frac 6 3)+f(\frac 6 6)
  • g(7)=f(71)f(77)g(7)=f(\frac 7 1)-f(\frac 7 7)
  • g(8)=f(81)f(82)g(8)=f(\frac 8 1)-f(\frac 8 2)
  • g(9)=f(91)f(93)g(9)=f(\frac 9 1)-f(\frac 9 3)
  • g(10)=f(101)f(102)f(105)+f(1010)g(10)=f(\frac {10} 1)-f(\frac {10} 2)-f(\frac {10} 5)+f(\frac {10} {10})
  • g(11)=f(111)f(1111)g(11)=f(\frac {11} 1)-f(\frac {11} {11})
  • g(12)=f(121)f(122)f(123)+f(126)g(12)=f(\frac {12} 1)-f(\frac {12} 2)-f(\frac {12} 3)+f(\frac {12} 6)

感觉上是不是和前面的切木棍的问题很像?因为这个过程的本质就是容斥原理。

n=p1a1p2a2p3a3...pkakn=p_ 1^{a_ 1}p_ 2^{a_ 2}p_ 3^{a_ 3}...p_ k^{a_ k},则:

g(n)=g(n)=

f(n)f(n)

f(np1)f(np2)...f(npk)-f(\frac{n}{p_ 1})-f(\frac{n}{p_ 2})-...-f(\frac n {p_ k})

+f(np1p2)+f(np1p3)+...+f(npk1pk)+f(\frac n{p_ 1 p_ 2})+f(\frac n {p_ 1 p_ 3})+...+f(\frac n {p_ {k-1} p_ k})

...-...

+(1)kf(np1p2...pk)+(-1)^kf(\frac n {p_ 1 p_ 2 ... p_ k})

那么我们可以开始定义了!

μ(x)={1x=1(1)kx=i=1kpi,gcd(pi,pj)=1,piP0others\mu(x)=\left\{\begin{matrix} 1 & x=1\\ (-1)^k & x=\prod_ {i=1}^{k} p_ i,gcd(p_i,p_j)=1,p_ i\in P\\ 0 & others \end{matrix}\right.

就可以得到

f(n)=dng(d)g(n)=dnμ(d)f(nd)f(n)=\sum_ {d|n}g(d)\Leftrightarrow g(n)=\sum_ {d|n} \mu(d) \cdot f(\frac{n}{d})

这个就是上面的g(n)g(n)的表达式了。这个μ(x)\mu(x)称为莫比乌斯函数,过程叫莫比乌斯反演。

数学形式想表达的意思就是,如果一个数为某个非1的平方的倍数,那么函数值为0;否则,如果质因数个数为奇数,函数值为-1,若因数个数为偶数,函数值为1。定义1的函数值为1。

O(n)O(n)求莫比乌斯函数

#include <iostream>
#include <cstdio>
#include <cstring>
#define N 10000010
using namespace std;
int mu[N],prime[N],ptop=0;
bool np[N];
int main(){
	memset(np,0,sizeof(np));
	int n;
	scanf("%d",&n);
	mu[1]=1;
	for(int i=2;i<=n;i++){
		if(!np[i]){
			prime[ptop++]=i;//1
			mu[i]=-1;
		}
		for(int j=0;j<=n&&i*prime[j]<=n;j++){
			np[i*prime[j]]=true;
			if(i%prime[j]==0){
				mu[i*prime[j]]=0;//2
				break;
			}else{
				mu[i*prime[j]]=-mu[i];//3
			}
		}
	}
	printf("%d",phi[n]);
}

其他形式

稍微思考一下,列一下表,可以发现一些其他常用形式:

  • f(n)=ndg(d)g(n)=ndf(d)μ(dn)f(n)=\sum_ {n|d}g(d)\Leftrightarrow g(n)=\sum_ {n|d}f(d)\cdot\mu(\frac{d}{n})
  • f(n)=dng(d)g(n)=dnf(d)μ(nd)f(n)=\prod_ {d|n}g(d)\Leftrightarrow g(n)=\prod_ {d|n}f(d)^{\mu(\frac{n}{d})}
  • f(n)=ndg(d)g(n)=ndf(d)μ(dn)f(n)=\prod_ {n|d}g(d)\Leftrightarrow g(n)=\prod_ {n|d}f(d)^{\mu(\frac{d}{n})}

在实际做题的时候我还发现反演不仅仅有这几种形式,只要是与约倍质和问题有关的套一套觉得差不多都可以用。

应用

莫比乌斯反演是非常强大的数论工具,能解决很多容斥原理的问题与约倍质和问题。如果一个函数容易用来求答案,一个容易直接求,而且有上述关系,则可以用莫比乌斯反演。

实例1

证明dnμ(d)={1n=10n>1\sum_ {d|n}\mu(d)=\left\{\begin{matrix} 1 & n=1\\ 0 & n>1 \end{matrix}\right.

这个式子其实是莫比乌斯反演可行的原因,但是我在这里只想用结论来证明这个式子。

设有常函数F(n)=1F(n)=1f(n)f(n)满足F(n)=dnf(d)F(n)=\sum_ {d|n}{f(d)}

易得f(n)={1n=10n>1f(n)=\left\{\begin{matrix} 1 & n=1\\ 0 & n>1 \end{matrix}\right.

f(n)=dnF(d)μ(nd)=dnμ(d)f(n)=\sum_ {d|n}F(d)\cdot\mu(\frac{n}{d})=\sum_ {d|n}\mu(d)

证毕。

实例2

统计有多少对(x,y)(x,y)互质。其中1xn,1ym1\leq x\leq n,1\leq y \leq m

F(d)=i=1nj=1m[dgcd(i,j)]F(d)=\sum_ {i=1}^{n}\sum_ {j=1}^{m}[d|gcd(i,j)]

f(d)=i=1nj=1m[d=gcd(i,j)]f(d)=\sum_ {i=1}^{n}\sum_ {j=1}^{m}[d=gcd(i,j)]

FFff的关系为

F(x)=xdf(d)F(x)=\sum_ {x|d}f(d)

反演!

f(x)=xdμ(dx)F(d)f(x)=\sum_ {x|d}\mu(\frac{d}{x})F(d)

=xdμ(dx)i=1ndj=1md1=\sum_ {x|d}\mu(\frac{d}{x})\sum_ {i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_ {j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}1

=xdμ(dx)ndmd=\sum_ {x|d}\mu(\frac{d}{x})\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor

所以

Ans=f(1)=i=1min(n,m)μ(d)nimiAns=f(1)=\sum_ {i=1}^{min(n,m)}\mu(d)\left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{i}\right\rfloor

i<ni<\sqrt{n}时只有n\sqrt{n}种取值,i>ni>\sqrt{n}ni\left\lfloor\frac{n}{i}\right\rfloor只有n\sqrt{n}种取值。对mm同理。预处理μ(x)\mu(x)前缀和,单次询问时间复杂度为O(2n+2m)O(2\sqrt{n}+2\sqrt{m})

BZOJ2301

实际要求$$f(d)=\sum_ {i=1}^{n}\sum_ {j=1}^{m}[d=gcd(i,j)]$$

由上一例有$$f(x)=\sum_ {x|d}\mu(\frac{d}{x})\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor$$

d=txd=tx

f(x)=t=1min(n,m)xμ(t)ntxmtxf(x)=\sum_ {t=1}^{\left\lfloor\frac{min(n,m)}{x}\right\rfloor}\mu(t)\left\lfloor\frac{n}{tx}\right\rfloor\left\lfloor\frac{m}{tx}\right\rfloor

于是可以和上一题一样快地求出来了。

BZOJ2818

还是先用上题的结论得到

Ans=pPpdμ(dp)nd2Ans=\sum_ {p\in P}\sum_ {p|d}\mu(\frac{d}{p})\left\lfloor\frac{n}{d}\right\rfloor^2

=d=1npd,pPμ(dp)nd2=\sum_ {d=1}^{n}\sum_ {p|d,p\in P}\mu(\frac{d}{p})\left\lfloor\frac{n}{d}\right\rfloor^2

=d=1nnd2pd,pPμ(dp)=\sum_ {d=1}^{n}\lfloor\frac{n}{d}\rfloor^2\sum_{p|d,p\in P}\mu(\frac{d}{p})

λ(x)=px,pPμ(xp)\lambda(x)=\sum_{p|x,p\in P}\mu(\frac{x}{p}),我们需要O(n)O(n)预处理出这个函数才能得到答案。

求和的每一项可以看作是把xx质因数分解之后抽掉一个质数。根据莫比乌斯函数性质,大部分函数值都为0.只有少部分会剩余1。若λ(x)0\lambda(x)\neq 0,则它必须满足一下条件之一:

  • μ(x)0\mu(x)\neq 0。这说明xx里面是由若干个质数组成的,除掉一个质数后还是由若干个质数组成的。设xxkk个质数的积,则λ(x)=(μ(x))k\lambda(x)=(-\mu(x))*k
  • pP,μ(xp)0\exists p\in P,\mu(\frac{x}{p})\neq 0。这样只要用p除x之后的数对答案就有贡献,用x除以其他的质数对答案没有贡献。λ(x)=μ(xp)\lambda(x)=\mu(\frac{x}{p})

综合上述两点,很容易就可以把λ(x)\lambda(x)的计算融入到线性筛当中。O(n)O(n)搞定。

BZOJ2440

这题就比较不典型了。首先二分答案xx,统计区间[1,x][1,x]有多少个不是完全平方数倍数的数。设F(n)F(n)n2n^2倍数的个数。

Ans=F(1)F(2)F(3)F(5)+F(6)F(7)+F(10)...Ans=F(1)-F(2)-F(3)-F(5)+F(6)-F(7)+F(10)-...

=i=1xμ(i)F(i)=\sum_ {i=1}^{x}\mu(i)F(i)

=i=1xμ(i)xi2=\sum_ {i=1}^{x}\mu(i)\lfloor\frac{x}{i^2}\rfloor

因为i>xi>\sqrt{x}时的求和项对答案都没有贡献了,所以二分判断时只需要O(n)O(\sqrt{n})的复杂度。

avatar
Kerry Su