51Nod2026 Gcd and Lcm

题意：定义数论函数 。

给出 ，求：

答案对 取模，，时限 。

---

这是个抖机灵题。

• 引理：对于任意积性函数，都有 。

  证明：对于 的情况，有 。

  则 。

  ，所以上式 。

  不难使用唯一分解定理和积性将结论扩展到全体正整数。

---

由引理可知 问题变为求解一次 的前缀和，那么可以使用 的块筛配合整除分块得到。

注意到 ，可以使用杜教筛求解 的块筛。

复杂度 。