题目相当于重新定义了一下
φ
和
μ
，只不过和原定义有一些区别。 首先可以求出第一问和第二问，这等价于在所有奇质因子中取奇数个（偶数个）互不相同的奇质因子的方案数，直接dp即可，注意
φ
函数是积性函数，直接乘起来即可。 第三问实际上就是所有方案的数量减去前两种方案，同样也可以dp直接求解。但是注意由于
φ
不是完全积性函数，所以当一个质因子是次数是一次时乘上的是
φ(x)
，二次乘上的是
φ(x)∗x
，也就是说后来每次多乘一个x。那么最后化简之后得到的就是
k∗(1+x+x2+...+xn)
类似于这样一个形式，考虑到这东西没法直接求（模数不互质），所以可以用【POJ 1845】的方法二分求解答案。 UPD：看了题解才发现第三问的总答案可以直接用莫比乌斯反演求出来，就是m-1。。。给跪了。。。
