计蒜客 38226 – tsy’s number

题目链接:计蒜客 38226 – ICPC 2019 南昌全国邀请赛(网络赛)G题

题目要求

$$ \sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k = 1}^{n} \frac{\varphi(i) \varphi(j^2) \varphi(k^3)}{\varphi(i)\varphi(j)\varphi(k)} \varphi({\rm gcd}(i,j,k)) $$

根据欧拉函数的定义(注意不是因为积性函数的性质),对分式部分约分,上式等于

$$  \begin{aligned} & \sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k = 1}^{n} j k^2 \varphi({\rm gcd}(i,j,k))  \\ =& \sum_{d = 1}^{n} \varphi(d) \sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k = 1}^{n} j k ^2 [{\rm gcd}(i,j,k) = d]  \\ =& \sum_{d = 1}^{n} \varphi(d)  \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{k = 1}^{\lfloor \frac{n}{d} \rfloor} (jd) (kd)^2 \sum_{t|{\rm gcd}(i,j,k)} \mu(t) \\ = & \sum_{d = 1}^{n} \varphi(d) d^3  \sum_{t = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) \sum_{t | i}^{i \leq \lfloor \frac{n}{d} \rfloor} \sum_{t | j}^{j \leq \lfloor \frac{n}{d} \rfloor} j \sum_{t | k}^{k \leq \lfloor \frac{n}{d} \rfloor}k^2 \\ =& \sum_{d = 1}^{n} \varphi(d) d^3  \sum_{t = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(t)  \lfloor \frac{n}{td} \rfloor \sum_{j = 1}^{\lfloor \frac{n}{td} \rfloor} (jt) \sum_{k = 1}^{\lfloor \frac{n}{td} \rfloor}(kt)^2  \end{aligned} $$

令$td = u$,则上式子等于

$$ \sum_{d = 1}^{n} \varphi(d) d^3 \sum_{d | u}^{u \leq n} \mu(\frac{u}{d})  \lfloor \frac{n}{u} \rfloor \sum_{j = 1}^{\lfloor \frac{n}{u} \rfloor} (j\frac{u}{d}) \sum_{k = 1}^{\lfloor \frac{n}{u} \rfloor}(k\frac{u}{d})^2  $$

整理得

$$ \sum_{u = 1}^{n} u ^ 3 \sum_{d | u} \varphi(d) \mu(\frac{u}{d}) \lfloor \frac{n}{u} \rfloor \sum_{j = 1}^{\lfloor \frac{n}{u} \rfloor}j \sum_{k = 1}^{\lfloor \frac{n}{u} \rfloor}k^2  $$

设$g(x) =x \sum_{j = 1}^{x}j \sum_{k = 1}^{x}k^2$,$f(x) = (\varphi * \mu)(x)$。则上式等于

$$  \sum_{u = 1}^{n} u^3 f(u) g(\lfloor \frac{n}{u} \rfloor )  $$

其中,对$j$和$k^2$求和可以使用等差数列求和公式和平方和公式很快算出,故$g(x)$可以快速计算。而$f(x)$需要预处理出来。由于$\varphi$和$\mu$均为积性函数,所以$f(x)$也为积性函数,考虑线性筛。

  • 当$x$为素数时,$f(x) = \mu(1) \varphi(x) + \mu_(x) \varphi(1) = x – 2$
  • $x = i \times p_j$
    • $ p_j \nmid i $,此时${\rm gcd}(i, p_j) = 1$,$f(i \times p_j) = f(i) f(p_j)$
    • $p_j | i$,考虑$f(p^{k + 1})$和$f(p^k)$的关系,如下

根据欧拉函数和莫比乌斯函数的定义

$$f(p^k) = \mu(1)\varphi(p^k) + \mu(p) \varphi(p^{k – 1}) =p^{k – 2} (p – 1)^2 $$

同理

$$ f(p^{k+1}) = p^{k – 1} (p – 1)^2 $$

得到$f(p^{k+1}) = p f(p^k)$。但是要注意这里推$f(p^k)$的时候结果是$k \geq 2$的情况,所以边界条件是$k = 2$,$f(p^2) = p^2 – 2p + 1$。这里要维护 ${\rm low}(i) = p_{1}^{a_1}$ ,一般积性函数筛法套路,可参考我的笔记 积性函数与线性筛 。还有一个坑点就是这题取模不能用逆元做,$a$在模$p$意义下逆元存在的条件是${\rm gcd}(a, p) = 1$。

 

 

1
说点什么

avatar
50
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 计蒜客 38226 – tsy’s number […]