[BZOJ3994/Luogu3327][SDOI2015]约数个数和(莫比乌斯反演,数论分块,线性筛)

发布于 2018-01-17  172 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3994/Luogu3327][SDOI2015]约数个数和(莫比乌斯反演,数论分块,线性筛)

Description

设d(x)为x的约数个数,给定N、M,求
[BZOJ3994/Luogu3327][SDOI2015]约数个数和(莫比乌斯反演,数论分块,线性筛)

Http

BZOJ
Luogu

Tag

莫比乌斯反演,数论分块,线性筛

题目大意

求\( \sum_{i=1}^{n} \sum_{j=1}^{m} d(ij) \),其中\( d(x) \)表示\( x \)的约数个数

解决思路

首先观察\( d(ij) \),这个式子我们不好处理。假设我们枚举\( u|i,v|j \),那么\( u*\frac{m}{v} \)就一定对\( d(ij) \)有\( 1 \)的贡献。
那么式子是不是就变成
\[ \sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{u|i} \sum_{v|i} \]
显然不是的。这样会算重。具体来说,设$$p$$为质数,若\( u'=u*p \),\( v'=v*p\),那么\( u'\)与\(v'\)对答案的贡献会与\(u\)和\(v\)重复,即\(u'* \frac{m}{v'}=u*p * \frac{m}{v*p}=u*\frac{m}{v}\)
所以我们发现,对于这个式子,应该要求$$u,v$$互质,即\(gcd(u,v)==1\)
结合上面的分析,我们可以得到这个初始式子
\[Ans=\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{u|i} \sum_{v|j} [gcd(i,j)==1]\]
把\(u,v\)提到前面来,因为\(i\)是\(u\)的倍数,在\([1..n]\)内一共有\(\lfloor \frac{n}{u} \rfloor\)这么多个\(u\)的倍数,那么也就有这么多个给\(u\)的代价,\(v\)的分析也是同理,所以得到
\[Ans=\sum_{u=1}^{n} \sum_{v=1}^{m} \lfloor \frac{n}{u} \rfloor * \lfloor \frac{m}{v} \rfloor [gcd(u,v)==1]\]
接下来莫比乌斯反演
设\[f(x)=\sum_{u=1}^{n} \sum_{v=1}^{m} \lfloor \frac{n}{u} \rfloor * \lfloor \frac{m}{v} \rfloor [gcd(u,v)==x]\]
设\[g(x)=\sum_{x|d}^{n} f(d) \\ =\sum_{u=1}^{n} \sum_{v=1}^{m} \lfloor \frac{n}{u} \rfloor * \lfloor \frac{m}{v} \rfloor [x|gcd(u,v)] \\ =\sum_{u=1}^{n/x} \sum_{v=1}^{m/x} \lfloor \frac{n/x}{u} \rfloor * \lfloor \frac{m/x}{v} \rfloor [1|gcd(u,v)]\]
\([1|gcd(u,v)]\)显然成立,所以
\[g(x)=\sum_{u=1}^{n/x} \sum_{v=1}^{m/x} \lfloor \frac{n/x}{u} \rfloor * \lfloor \frac{m/x}{v} \rfloor\]
现在的问题就变成,如何快速地求\(\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor\) ?
考虑\(\lfloor \frac{n}{i} \rfloor\)的概念,它就是\(n\)内有多少个\(i\)的因数。而把这些次数累加起来,是不是就是\(1\)到\(n\)的约数个数和?
形式化的,设\(F(x)\)表示数\(x\)有多少个约数,则有\(\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor=\sum_{i=1}^{n} F(i)\)。非常巧妙。
而\(F(x)\)是积性函数,可以线性筛,这样我们就把求解\(\sum \lfloor \frac{n}{i} \rfloor\)的复杂度由\(O(n*\sqrt{n})\)降到了\(O(n)\)。
具体来说,\(F(x)\)可以这样求。
根据唯一分解定理\(x=\prod p_{i}^{a^i}\),其中\(p\)为质数。
那么我们可以得到求解单个\(F(x)\)的方法,即\(F(x)=\prod ({a^i}+1)\)。知道这个式子,对于我们下面的推导有帮助。
接下来分类讨论,设\(p\)为质数
首先\(F(p)\)很好求,它就是\(2\)
再来考虑\(F(p*i)\ [gcd(p,i)==1]\),这个也很好求,根据积性函数的性质,\(F(p*i)=F(p)*F(i)\)
关键是\(F(p*i)\ [gcd(p,i)==p]\)的情况。由于\(i\)中已经有了\(p\),形式化地,设\(i=i'*p^k\),那么在\(F(i)\)中已经乘进去了\((k+1)\)这一项。我们若想得到\(F(p*i)\),那么就把\(F(i)\)除掉\((k+1)\)这一项再乘以\((k+2)\)。具体来说,我们对于每一个\(i\)再记录一个\(Low(i)\)表示把\(i\)唯一分解后最小的质因子\(p_1\)的指数,那么\(F(p*i)=F(i)/(Low[i]+1)*(Low[i]+2)\)
现在,我们就可以\(O(1)\)地求\(g(x)\)了。回到莫比乌斯反演。
\[f(x)=\sum_{x|d} \mu(\frac{d}{x}) g(d) \\ = \sum_{x|d} \mu(\frac{d}{x}) \sum_{u=1}^{n/d} \lfloor \frac{\frac{n}{d}}{u} \rfloor \sum_{v=1}^{m/d} \lfloor \frac{\frac{m}{d}}{v} \rfloor\]
最后把我们要求的$$f(1)$$带进去
\[f(1)=\sum_{i=1}^{n} \mu(i) \sum_{u=1}^{n/i} \lfloor \frac{\frac{n}{i}}{u} \rfloor \sum_{v=1}^{m/i} \lfloor \frac{\frac{m}{i}}{v} \rfloor\]
后面一块是可以\(O(1)\)求的,那么我们把前面分块,预处理\(\mu(i)\)的前缀和就可以了。
预处理复杂度\(O(n)\)
单次询问复杂度\(O(\sqrt{n})\)

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3994/Luogu3327][SDOI2015]约数个数和(莫比乌斯反演,数论分块,线性筛)


HNCJ OIer