日记 - 伊埃斯的博客站

今天是民国 114 年 5 月 14 日。

纯恶心人的题。谁用 C++ 写谁有病。

口胡一下发现当且仅当选出来的 $l_i$ 的 $\gcd$ 为 $1$ 的时候才会是可行的。于是我们直接设 $dp_i$ 表示把 $\gcd$ 干成 $i$ 的最小代价。转移就是 $dp_{j,\gcd(j,l_i)} \leftarrow dp_j + c_i$ 。用 map 存下来就行。

我们首先把 $a,b$ 都除以一个 $\gcd(a,b)$ 把他们变得互质。 $a,b$ 能通过这种操作变得某个为 $0$ 当且仅当这时的 $a + b = 2^k$ 。证明如下：

充分性：进行一次操作后，无论较小值是谁， $a,b$ 在二进制下的后缀 $0$ 个数都是增加的，这样最终就会变成 $2^k$ 。
必要性：手玩一下样例。

于是就是喜闻乐见的打代码时间了。

根据常识，我们发现 $\binom{n}{k}$ 的 $k$ 不会大于 $30$ ，于是我们直接枚举 $k$ ，因为在 $k$ 不变的情况下 $\binom{n}{k}$ 随 $n$ 单增，我们直接二分 $n$ 然后统计答案。

记得排序和去重。

~~野人的事情让野人自己想去~~

我们发现这玩意长得跟个粑粑同余方程似的，于是直接枚举 $m$ ，再枚举 $i,j$ 两个野人，exgcd 解出最小的 $x$ ，如果 $x$ 小于等于 $\min(l_i,r_i)$ ，就说明他们会打架，否则就可行。

明日目标： $140$ 。

Thanks for reading!

周三 5月 14 2025

376 字 · 2 分钟