AC. 梦想

frank_c1

[BZOJ 1101] Zap

发布于2016年01月04日 | 暂无评论 | 657阅读 | 数论,莫比乌斯反演

题目描述

FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d。作为FGD的同学,FGD希望得到你的帮助。

输入格式

第一行包含一个正整数n,表示一共有n组询问。(1<=n<= 50000)接下来n行,每行表示一个询问,每行三个正整数,分别为a,b,d。(1<=d<=a,b<=50000)

输出格式

对于每组询问,输出一个正整数,表示满足条件的整数对数。

题目解析

无限膜拜莫比乌斯反演和分块。

首先对题目条件做一个变换。令a' = a/k,b' = b/k,则根据最大公约数的性质,有

\sum\limits_{i = 1}^a {\sum\limits_{j = 1}^b {[\gcd (i,j) =  = k]} }  \Leftrightarrow \sum\limits_{i = 1}^{a'} {\sum\limits_{j = 1}^{b'} {[\gcd (i,j) =  = 1]} }

观察上式,既有i,j互质,那么我们可以作进一步推导:

\begin{aligned} \sum\limits_{i = 1}^{a'} {\sum\limits_{j = 1}^{b'} {[\gcd (i,j) =  = 1]} } & = \sum\limits_{i = 1}^{a'} {\sum\limits_{j = 1}^{b'} {\sum\limits_{d{\kern 1pt} |{\kern 1pt} \gcd (i,j)} {\mu (d)} } } \\ & = \sum\limits_{i = 1}^{a'} {\sum\limits_{j = 1}^{b'} {\sum\limits_{d{\kern 1pt} |{\kern 1pt} i\& \& d{\kern 1pt} |{\kern 1pt} j} {\mu (d)} } } \\ & = \sum\limits_{d = 1}^{\min \{ a',b'\} } {\mu (d)\left\lfloor {\frac{{a'}}{d}} \right\rfloor } \left\lfloor {\frac{{b'}}{d}} \right\rfloor \end{aligned}

推导至(1)式使用了莫比乌斯函数的性质,(2)式运用乘法原理,变换求和指标,得到(3)式。至此,我们所求的结果可以用线性时间求出。

但是询问有50000个,这样做还是超时,考虑优化。注意到{\left\lfloor {\frac{{a'}}{d}} \right\rfloor }的取值最多只有2\sqrt a' 个,{\left\lfloor {\frac{{b'}}{d}} \right\rfloor }同理。于是可以分块,把取值相同的一段合并一起算。用O(n)预处理莫比乌斯函数及其前缀和,一次询问只需O(\sqrt n )时间,至此问题成功解决。

利用本题的思想,还可以解决类似的2301,此处不再展开。