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

给出基础结论：

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)

发现函数只在

1

处有取值，函数应该是

\epsilon(i)=[i==1]

，那么

f(i)=mu(i)

发现取值比较小，发现

g(p^k)=k+1

，那么函数应该是

d(i)=\sum_{d} [d\mid i]

，则

f(i)=1

。

发现在

x=1

处

g(i)=0

所以

f(i)=0

。

发现数据是~~棍母状物~~随机的，但

k\le 100000\land \forall i\le k,i\ appears

，那么直接暴力。

进行两次反演，发现

f'(i)=\varphi(i)^2

，带入求

f(n)

，直接暴力求值。

反演后发现

f(p^k)=p^{2k-1}

，直接暴力求值。

g(i)=i^2,f(i)=\sum_{j\mid i}j^2\mu(\frac i j)

，发现不好操作，尝试利用积性，先分解质因数。

f(p^k)=\sum_{j\mid i}j^2\mu(\frac {p^k} j)

，所以只有

j=p^k,j=p^{k-1}

时

\mu

有值且可知，则

f(p^k)=p^{2k}-p^{2k-2}=p^k(1-\frac 1 p^2)

。

使用高效的质因数分解可以通过。

经过反演，猜测他是一个多项式，使用差值得出

f(x)=114x^3+514x^2+1919x+810

。

经过观察发现

f(i)=i^2\bmod 3

文章操作