CVBB ACM Team

这是本文档旧的修订版！

---

注意到 F(n) 是积性函数，所以可以拆开计算

考虑生成函数$G_p(x)=F(p^0)+F(p^1)x+\ldots$

那么$G_p(x)=(\phi(p^0)+\phi(p^1)+\ldots)^m=(\frac{1-x}{1-px})^m$

最终 $G$ 的生成函数就是 $\prod_iG_{p_i}(x)$

$G$ 的形式是分式，可以写成线性递推，我们可以在 $O(tm\log t\log N)$ 求出这个线性递推的第 $N$ 项。

由于质数个数不多，所以可以通过。