计蒜客 A1956 – Sum

题目链接:ICPC 2018 南京赛区网络预赛J题,计蒜客 A1956

去年网络赛队友打表+埃筛900+ms卡过1000ms时限,今年学习过数论函数求和的各种姿势发现$f = \mu^2 * \mu^2$,不禁感慨狄利克雷卷积之奇妙。

根据题意,$f(n)$是将$n$分解成两个无平方因子数的乘积的方案数$a \times b$和$b \times a$算不同情况,即

$$f(n) = \sum_{d | n} \mu^2(d) \mu^2(\frac{n}{d})$$

那么可以这样化简目标式

$$ \begin{aligned} & \sum_{i = 1}^{n} f(i) \\ =& \sum_{i = 1}^{n} \sum_{d | i} \mu^2 (d) \mu^2 (\frac{i}{d}) \\ =& \sum_{d = 1}^{n} \sum_{d | i}^{1\leq i \leq n} \mu^2(d) \mu^2(\frac{i}{d}) \\ = & \sum_{d = 1}^{n} \mu^2 (d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \mu^2 (i) \end{aligned} $$

那么只需要线性筛预处理出$\mu^2(n)$的前缀和,然后整除分块即可。

这里预处理的复杂度为$O(n)$,单次询问的复杂度为$O(\sqrt{n})$,注意这里的$n$比较大,全开long long会TLE,由于莫比乌斯函数涉及到的数值不大,可以开int,并且使用一些卡常技巧。

实际上,这题还有询问$O(1)$的做法。$\mu^2 * \mu^2$本身是积性函数,可以使用线性筛筛出,下面对$f(n)$进行分类讨论:

  • $n = 1$,根据积性函数性质$f(1) = 1$
  • $n$为质数,$f(n) = 2$,只能拆成$1 \times n$和$n \times 1$
  • $n = i \times p_j$
    • $p_j^2 | i$ 时,$i \times p_j$中至少包涵3个$p_j$,无论是$0+3$还是$1+2$地分解,均会产生平方因子,故$f(n) = 0$
    • 否则$i \times p_j$只含两个$p_j$,可以看作将$i$拆分成$a \times b$,然后两边各放入一个$p_j$,故$f(n) = f(\frac{n}{p_j})$

由此可以线性筛$O(n)$预处理,$O(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

[…] 计蒜客 A1956 – Sum […]