版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "题解 - [LOJ 6053] 简单的函数" categories:

题目链接

<!-- more -->

题意简述

求积性函数 $f$ 的前缀和, 其中 $f(p^q)=p\oplus q,~p\in\text{Prime}^+$

解题思路

不难发现

$$ f(p)=p+(-1)^{[p\ne2]},~\forall p\in\text{Prime}^+ $$

我们令

$$ g(n)=\varphi(n) $$

注意到 $f(2)\ne g(2)$, 但 $f(p)=g(p),~\forall p\in\text{Prime}^+\setminus{2}$, 看似直接暴力会使得求解的 $h$ 会大幅增加

实际上要暴力的所有值的集合只是变成了

$$ {x\in[1,n]{\mathbb{N}}:x~\text{is}~\text{powerful}~\text{number}}\cup 2{x\in[1,n]{\mathbb{N}}:x~\text{is}~\text{powerful}~\text{number}} $$

复杂度不变

复杂度

$O(n^r+\sqrt n\log n)$, 其中

代码参考

<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb cpa_cpp title:LibreOJ_6053 LibreOJ/6053/0.cpp %} </details>