题意
给定 \(n\)，先进行 \(m\) 次操作，每次给定 \(p,x\)，进行 \(\forall j,jp\leq n,s_{jp}\gets s_{jp}+jx\)。
然后进行 \(q\) 次查询，每次对 \(x\) 查询 \(\sum\limits_{1\leq i,ix\leq n} is_{xi}\)。
- \(n\leq 10^9\)
- \(m,q\leq 2\times 10^5\)
- 保证 \(\prod p \prod x\) 的质因子数量不超过 \(10\)。
解法
记 \(X_d\) 为对 \(d\) 位置操作的所有权值之和。
那么答案即为 \(\sum\limits_{x\mid v} \dfrac{v^2}{x} \sum\limits_{d\mid v} \dfrac{X_d}{d}\)。
直接使用狄利克雷前（后）缀和可以做到 \(O(n\log\log n)\)，获得 65 分。
可以打表发现在这个数据范围下，包含不超过 \(10\) 个质因子的集合 \(S\) 大小最多在 \(2\times 10^5\) 这个数量级。
所以上式中 \(\sum\limits_{d\mid v}\dfrac{X_d}{d}\) 不同的 \(v\) 较少。
可以枚举 \(S\) 中的 \(v\)，然后乘上系数 \(\sum\limits_{iv\leq n} [\gcd(i,L)]i^2\) 其中 \(L\) 是这不超过 \(10\) 个质因子的乘积。
反演之后可以计算系数，有用的点值只有整除分块的位置，所以不超过 \(O(\sqrt{n})\)，但是对 \(S\) 中的元素打表可知最多点值只有 \(10^4\) 多一点个。
计算答案时的可以以不超过 \(10\) 个质因子为阶段 dp。（类似狄利克雷前（后）缀和）
复杂度 \(O(\sqrt{n}2^{10}+|S|\cdot 10)\)。