题解：P9920 「RiOI-03」变换，反演

_7thRC_CB_CRP_ · 2025-07-16 10:39:16 · 题解

Solution

给出基础结论：g(n)=\sum_{i\mid n}f(i)\land f,g \ is\ integrability\Rightarrow f(n)=\sum_{i\mid n}g(i)\mu(\frac n i)

Task 0

发现函数只在 1 处有取值，函数应该是 \epsilon(i)=[i==1]，那么 f(i)=mu(i)

Task 1

发现取值比较小，发现 g(p^k)=k+1，那么函数应该是 d(i)=\sum_{d} [d\mid i]，则 f(i)=1。

Task 2

发现在 x=1 处 g(i)=0 所以 f(i)=0。

Task 3

发现数据是棍母状物随机的，但 k\le 100000\land \forall i\le k,i\ appears，那么直接暴力。

Task 4

进行两次反演，发现 f'(i)=\varphi(i)^2，带入求 f(n)，直接暴力求值。

Task 5

反演后发现 f(p^k)=p^{2k-1}，直接暴力求值。

Task 6