codeforces gym102471 C Dirichlet k-th root

题目：

有$g=f^k$，其中这里的乘指的是狄利克雷乘积。
现在，已知g求f（f不一定为积性函数）

题解：

有$g(n)=f^k(n)$
对于这种公式，首先我们应该想到两种方法，
一种是$g^{\frac{1}{k}}(n)=f(n)$，对于这种方法只要找到合适的数进行类似快速幂的卷积即可
另一种则是从公式推导，不过不变的肯定是用类似快速幂的思路将k优化到log(k)。
公式推导如下：
设$$F^k(n,m)=\sum_{a_1a_2…*a_k=n,a_i<m}f(a1)f(a2)…*f(ak)$$

$$g(n)=f^k(n)=k*f(n)+F^k(n,n)$$

$$k*f(n)=g(n)-F^k(n,n)$$

因此我们只要知道了$F^k(n,n)$就能把$f(n)$求出来了。

$$F^{2k}(n)=\sum_{d|n,if( k==1)1<d<n}{F^{k}(d)F^{k}(\frac{n}{d} )}$$