LibreOJ#6181:某个套路求和题 – 题解

主要思路

好题目啊。

发现 \(f(x)\) 对于有平方因子的数都没有效益,所以我们只考虑 \(f(x) = \prod_{i = 1}^m p_i\)。那么很容易发现 \(f(x) = \prod_{r = 0}^m (-1)^{2^{(r – 1)}}\),所以:

\[ f(x) = \begin{cases} -1, x \in primes or x = 1 \\ 1, otherwise \end{cases} \]

继续阅读LibreOJ#6181:某个套路求和题 – 题解

「LibreOJ」#572. 「LibreOJ Round #11」Misaka Network 与求和 – 题解

主要思路

先考虑莫比乌斯反演?

\[ \begin{aligned} ans &= \sum_{i = 1}^n \sum_{j = 1}^n f(\gcd(i, j))^k \\ &= \sum_{d = 1}^n f(d)^k \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = d] \end{aligned} \]

经典化简:

\[ \begin{aligned} ans &= \sum_{T = 1}^n \lfloor \frac{n}{T} \rfloor^2 \sum_{x|T} \mu(x) f(\frac{T}{x})^k \end{aligned} \]

我们可以对这个 \(\lfloor \frac{n}{T} \rfloor^2\) 进行整除分块,所以问题的重心转移到了求后面那个 Dirichlet 卷积的前缀和身上。

继续阅读「LibreOJ」#572. 「LibreOJ Round #11」Misaka Network 与求和 – 题解

「LibreOJ」#6682. 梦中的数论 – 题解

主要思路

其实稍稍看一下,会发现 \([j|i][(j + k)|i]\) 满足的时候 \(k\) 并没有什么特别的限制,所以可以直接理解为选两个因数,然后就转化为了:

\[ \begin{aligned} & \sum_{i = 1}^n {\sigma_0(i) \choose 2} \\ =& \sum_{i = 1}^n \frac{\sigma_0^2(i) – \sigma_0(i)}{2}\end{aligned} \]

后面的那个 \(\sum \sigma_0(x)\) 可以直接数论分块,前面那个用 min_25 筛一下就好。有 \(f(p^k) = \prod (1 + c_i)^2\)。

继续阅读「LibreOJ」#6682. 梦中的数论 – 题解