594

[CF594D] REQ 题解 思路 用欧拉函数的公式来求解，可以发现，对于每一个质因数都只会做一次贡献，然后是区间查询，联想到 HH的项链 一题，考虑离线询问，按右端点排序，在树状数组里面维护最靠右的质因数的位置做贡献，然后区间积一下就有了。 注意质因数分解暴力做根号应该会爆，可以筛质数之后对质数 ......

由于本人在思索了很久后才把本题思路打通，所以为了帮助像我一样没有非常理解解法的人，我打算再将解法非常详细地叙述一遍，如果您无法理解解法，请跟着我再一步步将题目捋顺。 Step.1 解题意 题目要求其实很好理解，共给出 $n$ 个点的位置，A,B两个人轮流取点，A要求最后剩下的两个点尽量近，B要求最后 ......