牛客64C
哦，CNM，看错题了。
题意是如果某个位置为0以后在n的位置的出口就能打开，还是要回到n；并不是能从当前为0的位置立刻逃出。
根据直觉循环节来讲，如果要完整踩完一轮点(不一定要每个点都踩，可能会有踩不到的，或者说回到n)，跨过的距离和就是{\rm lcm}(n,d)，因为一步是d,所以要走{\rm lcm}(n,d)/d步，所以循环节长度是\gcd(n,d)，\forall k, \gcd(n,d)|k的点都要在这一轮里被踩一次，所以想出去要走的步数就是这些点里数最小的\times走一轮的步数。
\begin{aligned}
ans &= \sum_{d=1}^n\frac{n}{\gcd(n,d)}\min_{\gcd(n,d)|i}\{a_i\}\\
\end{aligned}
设\min_{\gcd(n,d)|i,i\leq n}\{a_i\}=g(\gcd(n,d))，考虑集中处理\gcd(n,d)=x的答案
\begin{aligned}
ans &= \sum_{d=1}^n\frac{n}{\gcd(n,d)}\min_{\gcd(n,d)|i}\{a_i\}\\
&=\sum_{d|n}g(d)\frac{n}{d}\sum_{i=1}^n[\gcd(n,i)==d]\\
&=\sum_{d|n}g(d)\frac{n}{d}\sum_{i=1}^{\frac{n}{d}}[\gcd(n,i)==1]\\
&=\sum_{d|n}g(d)\frac{n}{d}\varphi(\frac{n}{d})
\end{aligned}
因为本题只需要d|n的g(d)，所以直接枚举d的因数暴力d\times j, j\leq n即可，如果求\forall d, 1\leq d\leq n得话，需要先预处理质数，然后倒着对所有数从小到大乘质数表里的所有数。
for(int i = 1; i <= n; i++) g[i] = (int)a[i];
for(int i = n; i >= 1; i--) {
for(int j = 1; prime[j] * i <= n && j <= pcnt; j++) {
g[i] = std :: min(g[i], g[i * prime[j]]);
}
}
注意j限制质数表的上限pcnt，不然可能会做到>n的情况去，这个时候g就变成0了或者prime_j不存在，直接寄。
复杂度的话，考虑如果当前是做x的倍数，显然最大只能乘一个\frac{n}{x}，也就是p(\frac{n}{x})=\sum_{i\geq 2}^{n/x}[i\in \rm P]
直接进行积分
\begin{aligned}
\sum_{i\geq 2}^np(\frac{n}{i})&=\int_2^np(\frac{n}{x}){\rm d}x\\
&=\int_2^n\frac{n}{x(\ln n - \ln x)}{\rm d}x\\
&=\int_2^n\frac{n}{(\ln n - \ln x)}{\rm d}(\ln x)\\
&=-\int_2^n\frac{n}{(\ln n - \ln x)}{\rm d}(\ln n - \ln x)\\
&=-n\int_2^n\frac{1}{(\ln n - \ln x)}{\rm d}(\ln n -\ln x)\\
&=-n\ln (\ln n- \ln x)|_{2}^n
\end{aligned}
所以是O(n\ln \ln n)的，比较愉快，能做10^7
lg p5652
考虑一个位置x,a_x，如果只有这一个位置那显然在a_x\in \rm odd的情况下是先手必胜的
假设x这个位置先手必胜，那么在A跳到这个位置之前[x-m,x-1]的位置的时候，B可以直接跳到x来，那么B就可以直接获胜。这个时候[x-m,x-1]这连续的m个位置一定是先手必败的
同样的，如果在某个位置之后不存在先手必胜的位置，那这个位置被先定位先手必败。如果没有m的限制，只需要判定边界a_R是否为奇数即可；但是因为m的限制并不能一步跨越：如果在[x-m,x-1]之前存在一个最近的位置y\in[x-2m,x-m-1],a_y\in \rm odd,，在A跳到y之后接着B跳，因为这是[x-m,x-1]区间之前最近的先手必胜(奇数)点，所以下一个奇数点一定落在[x-m,x-1]，这个时候B必败，因此确定x作为必胜点之后，上一个必胜点就是\max y,y<x-m,a_y \in \rm odd的y；综上可以O(n)之内确定所有的先手必胜点
当有一个区间[L,R]，其中最后一个a_x \in \rm odd后面还有偶数点的时候，我们也默认这个点是必胜点：当取到0而后手无法做出行动时，后手被迫选择剩余的偶数点，这时后手被迫转为进入偶数点的先手，此时先手必败；而这个偶数点取完后，进入这个偶数点时的先手要么输掉，要么进入下一个偶数点，继续充当必败态。因此对于一个询问，只需要查询L能不能跳到最后一个x\leq R,a_x \in \rm odd即可。
注意到每次设对应的a_x为必胜态然后判断A是否必胜的时候是O(R-L)=O(Len)的，然而我们注意到对于每个点作为必胜态的时候，他左边的必胜态都是固定的；不断跳必胜态的过程可以类比成在树上暴跳father，因此查询是否必胜本质是在询问L是否为x的祖先，直接\rm dfs序维护即可(转化为判断是否在子树内)。
总复杂度O(n+q)