题面蛮长的，大概是定义了两个函数   嗯，t(1e5)和m(1-5)还有那些个素数是给定的，现在给你个1e9的N，让你算。那么第一很明显的是，欧拉函数是积性函数，而的公式是个迪利克雷卷积形式，所以显然也是积性函数，所以我们就可以得到  然后这个形式他就很想让人用生成函数。根据欧拉函数的性质.  因此   其实到这里都没什么难度，我们只要求出的系数就好了。题解说是线性递推，但是很多人（好吧只有我）不知道为什么能转化成线性递推。 然后那天在群里问，有人说展开，我会想起了斐波那契的生成函数解法，于是才想到。事实上是这样的将生成函数上线展开，设成这样。  然后移过来  (其实到这里参考生成函数求斐波那...