[HDU4746] Mophues (莫比乌斯反演,数论分块)

发布于 2018-01-14  12 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU4746] Mophues (莫比乌斯反演,数论分块)

Description

As we know, any positive integer C ( C >= 2 ) can be written as the multiply of some prime numbers:
\(C = p_1*p_2*p_3*...*p_k\)
which \(p_1, p_2 ... p_k\)are all prime numbers.For example, if \(C = 24\), then:
\(24 = 2*2*2*3\)
here, \(p_1 = p_2 = p_3 = 2, p_4 = 3, k = 4\)

Given two integers P and C. if k<=P( k is the number of C's prime factors), we call C a lucky number of P.

Now, XXX needs to count the number of pairs (a, b), which 1<=a<=n , 1<=b<=m, and gcd(a,b) is a lucky number of a given P ( "gcd" means "greatest common divisor").

Please note that we define 1 as lucky number of any non-negative integers because 1 has no prime factor.

Http

HDU

Tag

莫比乌斯反演,数论分块

题目大意

Fact(x)表示把x唯一分解后,分解出来的质因子的个数(注意,相同的质因子不算同一个),求\[\sum_{i}^{n} \sum_{j}^{m} [Fact(gcd(i,j))<=P] \]

解决思路

首先考虑Fact(x)这个函数,我们发现它是可以线性筛出来的,具体来说,根据其性质可以这样递推出来
p为质数
\[\begin{cases} Fact(p)=1 \\ Fact(p^k)=k \\ Fact(p*i)=Fact(i)+1 \end{cases}\]
由于对于每一个x=gcd(i,j),其Fact(x)是一定的,所以我们先不考虑这个质因子个数的限制。
设\[f(x)=\sum_{i}^{n} \sum_{j}^{m} [gcd(i,j)==x]\] \[g(x)=\sum_{x|d} f(d)\]
根据我们之前做过的题目(比如这里),可以知道g(x)=\lfloor \frac{n}{x} \rfloor * \lfloor \frac{m}{x} \rfloor,根据莫比乌斯反演,可以得到f(x)=\sum_{x|d} g(d)
假定我们最后要求的是\sum_{i} f(i)(也就是不考虑P的限制时的方案数),那么我们现在得到了一种O(n*\sqrt{n})的办法,就是枚举i算出每一个f(i)求和,而算f(i)的过程可以通过数论分块降到O(\sqrt{n})的复杂度。
很明显,对于题目的数据范围,这样的复杂度是不行的。考虑到是求和操作,我们来看一看每一个g(x)最后给答案贡献了多少次。
\[f(1)=\mu(\frac{1}{1})*g(1)+\mu(\frac{2}{1})*g(2)+\mu(\frac{3}{1})*g(3)...... \\ f(2)=\mu(\frac{2}{2})*g(2)+\mu(\frac{4}{2})*g(4)+\mu(\frac{6}{2})*g(6)...... \\ f(3)=\mu(\frac{3}{3})*g(3)+\mu(\frac{6}{3})*g(6)+\mu(\frac{9}{3})*g(9)...... \\ ...... \\ f(x)=\mu(\frac{1*x}{x})*g(1*x)+\mu(\frac{2*x}{x})*g(2*x)+\mu(\frac{3*x}{x})*g(3*x)......\\ =\mu(1)*g(1*x)+\mu(2)*g(2*x)+\mu(3)*g(3*x).....\]
可以发现,每一个数x给它的倍数d=kxg(d)贡献了\mu(j)的莫比乌斯系数,所以我们可以考虑线性推出这个系数的和。设F[d]表示g(d)前面莫比乌斯系数的和,那么枚举x的倍数d=kxF[d]+=\mu (\frac{d}{x})
最后我们把对质因子个数的条件放进去。先考虑要求质因子个数一定等于P的。这时候也就是说对于一个数x,它只能在给定的P与它的质因子个数相同的时候才能贡献,所以考虑把F[d]加一维变成F[d][p],表示x分解质因子个数为p时对x的倍数d=kxg(d)的贡献,那么就是F[d][Fact(x)]+=\mu(\frac{d}{x})
最后把条件再放宽,即质因子个数小于等于P的,那么求[p]这一维的前缀和即可。由于我们需要数论分块将复杂度,需要求[d]这一维的前缀和,所以我们求二维前缀和即可。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU4746] Mophues (莫比乌斯反演,数论分块)


HNCJ OIer 一枚