【记录】妙妙题
新坑。
arc136 e
\(1\) 到 \(n\) 的数，如果两个数不互质则从小到大连有向边，点带权，求一个权最大点集使没有两个点满足其中一个可以到达另一个。
sol
首先把 $1$ 选掉，考虑两个数 $x,y$ 互相可达的条件：- \(x\) 为偶数，\(y\) 为偶数：一定可达。
- \(x\) 为奇数，\(y\) 为偶数 则 \(x+minprime_x \leq y\)。
- \(x\) 为偶数，\(y\) 为奇数 则 \(x \leq y-minprime_y\)。
- \(x\) 为奇数，\(y\) 为奇数 则 \(x+minprime_x \leq y-minprime_y\)。
于是对于每个点表示出一个区间，如果 \(x\equiv 0\) 则为 \([x,x]\)，否则为 \([x-minprime_x+1,x+minprime_x-1]\)。
然后两个点有可达关系等价于它们弄出的区间不交，也就是说无可达关系等价于它们弄出的区间有交。
于是把点权加到对应区间然后取最大值即可。
record
为什么感觉自己就是把官方题解抄了一遍（）