P13940 [EC Final 2019] Dirichlet k-th root

庞数学家在上一次集训中学习了狄利克雷卷积。不过，相比深度强化学习，这对他来说太简单了。因此，他做了一些特别的事情。 如果 $f,g: \{1,2,\ldots,n\} \to \mathbb {Z} $ 是从正整数到整数的两个函数，则狄利克雷卷积 $f * g$ 定义为一个新函数： $$(f * g)(n) =\sum_{d \mid n}f(d)g \left(\frac {n}{d}\right) .$$ 我们定义函数 $g=f^k$ 的 $k$ 次幂为 $$ f^{k}=\underbrace {f * \dots * f} _{k~{\textrm {次}}}.$$ 在本题中，我们要求解逆问题：给定 $g$ 和 $k$，你需要找到一个函数 $f$，使得 $g=f^k$。 此外，还有一个额外的限制条件：$f(1)$ 和 $g(1)$ 必须等于 $1$。所有的算术运算都在 $\mathbb{F}_{p}$ 上进行，其中 $p=998244353$，也就是说，在狄利克雷卷积中，$(f * g)(n) =\left(\sum_{d \mid n}f(d)g \left(\frac {n}{d}\right)\right) \bmod p$。

第一行包含两个整数 $n$ 和 $k~(2\leq n\leq 10^5,1\leq k

如果无解，输出 $-1$。 否则，输出 $f(1), f(2), ..., f(n)$（$0\le f(i)

由 ChatGPT 4.1 翻译