p16241

📅 2026/7/15 23:24:39 👁️ 阅读次数 📝 编程学习
p16241

P16241

思路:

每次删最大值和他的因数,思考对于某一个数x,什么情况下会被删

1.x为最大值

2.x小于n的最大倍数即 $ n - n\bmod b$ 删掉时,删掉了x

因为x的最小倍数为 \(2x\) 所以如果 \(2x>n\) 就会导致x只能被第一种情况删掉即 \(n/2<x\) ,相反则 \(x<n/2\) 一定会先被x的最大倍数所删掉

我们可以在 \(n/2\)\(n\) 这个区间中考虑每一步操作,统计删i时,删掉的个数和删掉数的异或和,再从删除的倒顺序去考虑剩余的异或和

全部删光的异或和为0,每一次把先前剩余的异或和异或上这一步删除的异或和,就为没删除这个点剩余的异或和

提前预处理出这个

\(n<10^{18}\)时:

所有 \(<n/2\) 的数在还没有保留 B 个数时就全删掉了

最终剩下的一定是 最大的连续 B 个数:\(n/2+1∼n/2+B\)

直接用异或前缀和

时间复杂度为 \(O(maxb)\)