只说满分做法，部分分做法就是以下各部分的更慢做法而已。

首先预处理 $1\sim 2n$ 的 $\varphi$ 函数，这个结合线性质数筛即可。

由于 $\varphi(n),\varphi(2n),\varphi(n-K)$ 都不大于 $n$，因此游戏一定有终点必胜态 $1$，是公平组合游戏，以此利用记忆化搜索或者 dp 可以预处理所有点是先手必胜还是必败态。

设 $a_i$ 表示 $i$ 的先手必胜/必败态，设必胜是 $0$，必败是 $1$，那么对所有的 $a_r=0$，要求 $b_r=\max\limits_{l=1}^r\dfrac{\sum\limits_{i=l}^r a_i}{r-l+1}$ 。

设满足 $a_r=0$ 的 $r$ 有 $r_1,r_2,...,r_m$，则答案为 $\dfrac{\sum\limits_{i=1}^m(1-b_{r_i})}{m}$，保证 $m\ge 1$

快速求 $b_r$ 则直接根据点集 $(i,\sum\limits_{j=1}^i a_j)$ 求下凸壳相邻两点的最大斜率即可，使用线性的单调队列求法即可。

满分做法三个部分的时间复杂度均为线性，评价为小清新缝合题。

更详细的题目讲解见 https://zhuanlan.zhihu.com/p/691259649