[HDU5212]Code (莫比乌斯反演)

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


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

本文链接地址:[HDU5212]Code (莫比乌斯反演)

Description

WLD likes playing with codes.One day he is writing a function.Howerver,his computer breaks down because the function is too powerful.He is very sad.Can you help him?

The function:

Http

HDU

Tag

莫比乌斯反演

题目大意

求\[\sum_{i}^{n} \sum_{j}^{n} gcd(A[i],A[j])*(gcd(A[i],A[j])-1)\]

解决思路

换一个思路,考虑到值域直到\(10000\),所以可以开桶统计每一个数出现了多少次,记\(Cnt[i]\)表示数\(i\)出现了多少次。在值域里枚举,那么答案就是\[Ans=\sum_{i}^{10000} \sum_{j}^{10000} Cnt[i]*Cnt[j]*gcd(i,j)*(gcd(i,j)-1)\]
令\(f(x)=x*(x-1)\),构造$$g(x)$$,使$$f(x)=\sum_{d|x} g(d)$$,则根据莫比乌斯反演,可以得到$$g(x)=\sum_{d|x}\mu(\frac{x}{d}) f(d)$$。
这样有什么用呢?根据我们得到的$$g(x)$$,我们可以把对答案的求解式化成这个形式
\[Ans=\sum_{i}^{10000} \sum_{j}^{10000} Cnt[i]*Cnt[j]*\sum_{d|i,d|j} g(d)\]
为什么可以这样化呢?因为$$d|i,d|j$$保证了$$d$$一定是$$i,j$$的因子,而$$\sum_{d|x} g(d)=f(x)$$,所以就可以直接替换原来的$$gcd$$
那么接着我们把原来枚举$$i,j$$换成枚举$$d$$,即把后面的$$\sum$$换到前面来。考虑每一对$$i,j$$对$$d$$的贡献,那么式子可以这样列
\[Ans=\sum_{d}^{10000} \sum_{d|i}^{10000} \sum_{d|j}^{10000} Cnt[i]*Cnt[j] *g(d)\]
重新观察一下这个式子,既然我们把$$d$$已经提到外面了,那么里面枚举的$$i$$和$$j$$其实是一样的,那么我们可以把两次枚举合二为一
\[Ans=\sum_{d}^{10000} g(d) * {(\sum_{d|i} Cnt[i])}^2\]
这样,计算的复杂度就降到$$O(n\sqrt{n})$$

代码

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

本文链接地址:[HDU5212]Code (莫比乌斯反演)


HNCJ OIer