ARC 乱做

ARC136E

显然 \(1\) 没有出边，先选上

记 \(f(x)\) 为 \(x\) 的最小质因子，则 \(x-f(x)\) 是能到 \(x\) 的最大值，\(x+f(x)\) 是 \(x\) 能到的最小值

考虑两个点 \(x,y\) 何时可达：

• \(x\equiv0\pmod2,y\equiv0\pmod2\)：永远可达
• \(x\equiv0\pmod2,y\equiv1\pmod2\)：\(x\le y-f(y)\)
• \(x\equiv1\pmod2,y\equiv0\pmod2\)：\(x+f(x)\le y\)
• \(x\equiv1\pmod2,y\equiv1\pmod2\)：\(x+f(x)\le y-f(y)\)

简证一下第四种情况：若 \(x\) 能直接到 \(y\)，设 \(x=ap,y=bp\)（\(a,b\) 为奇数），那么 \(a；若 \(x\) 经过另一点 \(z\) 到达 \(y\)，那么 \(x+f(x)\le z\le y-f(y)\)

据此可以构造

• \(x\equiv0\pmod2\)：\(l(x)=r(x)=x\)
• \(x\equiv1\pmod2\)：\(l(x)=x-f(x)+1,r(x)=x+f(x)-1\)

那么 \(x\) 不能到 \(y\) 等价于 \([l(x),r(x)]\cap[l(y),r(y)]\ne\varnothing\)，枚举交集中的一个元素即可。时间复杂度 \(O(n)\)