POJ 3904 – Sky Code

题目链接:POJ – 3904

给出一个序列$a_n$, 求选出四个数并且四个数的最大公约数为1的情况数,根据莫比乌斯反演定理

$$\begin{aligned} & \sum_{u,v,p,q \in \{a_n\} } [{\rm gcd}(a_u, a_v, a_p, a_q) = 1]  \\ = & \sum_{u,v,p,q \in \{a_n\}}  \sum_{t | d} \mu (t) \end{aligned}$$

其中$d = {\rm gcd}(a_u, a_v, a_p, a_q)$,则调换求和次序,上式可化为

$$\sum_{t = 1}^{\max \{ a_n\} } \mu (t) {f(t) \choose 4}$$

其中$f(t)$为$\{a_n\}$中$t$的倍数的个数,求法类似埃筛。那么预处理出莫比乌斯函数的函数值,就可以在$O(k \log k)$的时间得到答案,其中$k = \max \{ a_n \} $。

 

说点什么

avatar
50
  Subscribe  
提醒