CF1355

$Div.2$ ,被炸鱼了.

直接按照题意暴力做,当某一位为 $0$ 时,后面操作都没用了,退出即可.

操作次数显然不会太多.

显然尽量先用 $e_i$ 比较小的人,记录一下剩了几个人,和后面的人一起用即可.

枚举 $z$ ,计算有多少对 $x+y>z$ ,分类讨论一下计算贡献即可.

也可以直接 FFT, 把 $x,y$ 对应的生成函数给卷起来计算 $x+y>z$ 的有多少对.

当 $S\ge 2N$ 时,可以构造出所有数都 $\ge 2$ 的方案,然后令 $K=1$ 即可.

否则显然无解.

记最后所有数都变成了 $x$ ,那么答案关于 $x$ 显然是一个先降后升的单峰函数.

三分,对于某个 $x$ ,算一下需要执行多少次 $+1$ ,多少次 $-1$ .

若 $M<A+B$ ,就用 $M$ 操作先尽可能抵消,剩下的用 $A,B$ 操作完成即可.

如果能求出 $X$ 各个质因子的次数,就能得到答案了,但 $10^9$ 内质数太多,无法准确询问出每一个质因子的次数.

考虑只确定 $\le p$ 的质数是否在 $X$ 中出现,记这部分质数乘积为 $X_1$ ,那么 $> p$ 的出现过的质数乘积 $X_2\le \frac{10^9}{X_1}$ .

当 $X_1\cdot p^3\ge 10^9$ 时,可以确定 $X_2$ 中含有的质因子个数不会超过 $2$ ,否则 $X_1\cdot X_2> X_1\cdot p^3\ge 10^9$ ,不合法.

那么 $X_2$ 部分的贡献不会超过 $4$ ,求出 $X_1$ 部分贡献后乘上 $2$ ,即可保证相对误差在 $2$ 倍内.

分类讨论一下,若 $X_1\le 3$ ,直接令 $X_1$ 部分贡献为 $4$ ,可以利用绝对误差 $\le 7$ 的标准通过测试.

若 $X_1> 3$ ,取 $p=630$ 有 $X_1\cdot p^3\ge 10^9$ ,如果对 $630$ 内所有质数都确定是否出现,需要 $19$ 次询问.

如果得到的 $X_1$ 只有不超过 $2$ 个质因数,我们用 $1$ 次询问即可确定它们具体的次数.

否则, $X_1$ 至少为 $2\times 3\times 5$ ,此时 $p\le 330$ , $11$ 次询问即可确定出现情况,再用 $\omega(X)\le 9$ 次询问确定具体次数.

这两种情况的询问次数都不会超过 $20$ .

最坏情况是 $X_1=1$ ,此时需要对 $\le 1001$ 内每个质数确定是否出现,经验算恰好需要 $22$ 次询问.