代码解释： * 预处理PK数组:使用快速幂计算每个数的K次幂模MOD。 * 线性筛法:同时计算每个数的最小质因子，利用积性函数性质高效计算H(N),H(N)H(N),H(N)H(N),H(N)表示对所有D∣N,Μ(D)∗(N/D)KD|N,Μ(D)*(N/D)^KD∣N,Μ(D)∗(N/D)K的和，通过线性筛保证O(N)O(N)O(N)时间复杂度。 * 前缀和优化:SUMHSUM_HSUMH 数组存储H的前缀和，支持O(1)O(1)O(1)区间和查询。 * 数论分块:对每个测试用例，通过整除分块将枚举次数从O(N)O(N)O(N)降至O(N)O(\SQRT N)O(N )。 方法:莫比乌斯反演，线性筛，狄利克雷卷积，前缀和(稍显多余) 防抄袭代码(仅供参考):