HDU 6428 (MultiSchool Round10 Problem 1003)

未分类

---

题意:
给定了$a,b,c$，求: $\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c \phi\left( gcd(i,j^2,k^3)\right)$
数据范围:$1\leq a,b,c \leq 10^7$

解析:
莫比乌斯反演: $\phi(n)=\sum_{d|n}\mu(d)(n/d),n=\sum_{d|n}\phi(d)$
狄利克雷卷积: $(f*g)(n)=\sum_{d|n}f(d)g(n/d)$

$$\begin{align*} \phi(n) &=\sum_{d|n}\mu(d)(n/d) \\ &= \sum_{d|n}\mu(d)\sum_{d'|n/d}\phi(d') \\ &= \sum_{dd'|n}\mu(d)\phi(d') \\ &= \sum_{d|n}\sum_{d'|d}\mu(d')\phi(d/d') \\ &= \sum_{d|n} (\mu*\phi)(d) \end{align*}$$

对于要求解的式子:

$$\begin{align*} ans &= \sum_{i=1}^a \sum_{j=1}^b \sum_{k=1}^c \phi \left( gcd(i,j^2,k^3) \right) \\ &= \sum_{i=1}^a \sum_{j=1}^b \sum_{k=1}^c \sum_{d|gcd(i,j^2,k^3)}(\mu*\phi)(d) \\ &= \sum_{d=1}^a(\mu*\phi)(d)\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c[d|gcd(i,j^2,k^3)] \\ &=\sum_{d=1}^a(\mu*\phi)(d)\sum_{i=1}^a [d|i] \sum_{j=1}^b [d|j^2] \sum_{k=1}^c [d|k^3] \\ &= \sum_{d=1}^a(\mu*\phi)(d) \lfloor\frac{a}{f_1(d)}\rfloor \lfloor\frac{b}{f_2(d)}\rfloor \lfloor\frac{c}{f_3(d)}\rfloor \\ \end{align*}$$

记$h(n)=(\mu*\phi)(n)=\sum_{d|n}\mu(d)\phi(n/d)$,可以证明$h(n)$是一个积性函数,而且有以下性质:

$$\begin{align*} h(1) &= 1 \\ h(p) &= p-2 \\ h(p^n) &= (p-1)^2p^{n-2} \\ h(p_1^{n_1}p_2^{n_2})&=h(p_1^{n_1})h(p_2^{n_2}) \\ &... \\ &... \end{align*}$$

$f_k(n)$是指使$n|x^k$的最小的正$x$,显然如果$n=\prod p_i^{a_i},f_k(n)=\prod p_i^{\lceil \frac{a_i}{k} \rceil }.$

以上几个函数均是积性函数,均可通过线性筛求出.
时间复杂度$O(a).$

原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=6428
$AC$代码:https://paste.ubuntu.com/p/rM72yGnTFk/