Luogu4466 [国家集训队] 和与积

题意：给出 ，求 ，时限 。

---

先观察 的充要条件。

显然 ，否则 ,那么 。

设 ，令 ，则 总之：。

---

• 将 同时除以 。

• 设 ，转而枚举 。

• 将 同时除以 。

• 将 加上 。

• 记 。

先求出整除位置的 的值，分块单求一个 ，总复杂度 。

接下来计算答案。枚举 并对 分块计算。单次分块复杂度为 ，求和可得复杂度为 不精细的处理可以做到 。