官方题解见 UOJ Long
Round #1 题解，这里介绍一下参赛大佬们提出的更简洁的做法。
题意：给出常数 ，定义积性函数 。
给出 ，求下列式子的值：
答案对 取模。
多组数据，，，，时限。
记积性函数 ，有 。
记 ，可以用 反演掉 。
其中 只需要求出 即可。
可以发现 ，所以所有 的 都必须满足 。
则有 由于 ，说明 是一个无平方因子数，且 的素因子在 中的次数都是偶数。因此，有 。
记 ，则有
。
可以发现，
是个积性函数（
分别积性，点乘仍然有积性），观察质数幂处的取值：
注意到 和 只有 倍数处的位置取值值不同，可以计算 。
当 时， ，则
当 时， ，则
。
当 时， ，则
。
如此反复，可归纳证明 。
则有 ：
注意到 有值的位置不多（不足
），可以暴力搜索出所有有值的位置。
那么问题就变为求出
的块筛（或称基本和组），官方题解中有 的做法。
下面也有一个
的做法，会更简洁一些 ：
首先显然有 ，根据 PN
相关理论，可以
求块筛。
具体地，构造 ，则 只在 PN 处有值。
不仅如此，可以证明 ， 只在平方数处有值。
记 ，则
用线性筛求出 内的
函数，然后可以整除分块 计算一个 。
若要求块筛，和线性筛复杂度平衡一下可以做到 。