「Summary」2022-07-11 做题记录

“大概联赛范围就会用到这些数论知识吧。”

2022-07-11

$\mathbb{CF510D}$

link
于是，写离散化到一半，想起了 map, 顺手写了一发，直接过了。
转化题意，给定 $l, c$ 两数组，满足限制 $\sum_{i = 1}^{n} a_i l_i = 1$ 并且使得 $\sum_{i = 1}^{n} c_i[a_i \not = 0]$，这个限制长得很像一个线性方程组，觉得是高斯消元，但是观察到右边为 $1$ ，那么有 zsj 不定方程定理 可以知道有解的唯一条件是 $\gcd(l) = 1$ ，这里的 $l$ 直接表示选出来的纸条长度集合。
有个最小值，考虑 $dp$ ， 可以自然想到定义 $dp_{i, j}$ 表示用前 $i$ 个数，目前的公约数为 $j$ 所花费的最小值。这个很好转啊， $dp_{i + 1, \gcd(j, l_i)} = \min\{dp_{i,j} + c_i\}$ 。第二维可以直接用 map 莽过去。

$\mathbb{CF1114F}$

link
对于这种把数论套到数据结构上的题，评价是 ： 毫无新意。
上一次做这种玩意还是去年同时期，聪慧的 TryMyEdge 把中国剩余定理套到了线段树上，真就无智商乱码题，结果我还写错。
首先观察到给了个 $x \le 300, a_i \le 300$ ，哦这个是不是看起来很厉害，意图明显得一比，素数个数直接被卡死了，顺手一筛，刚好，有 $62$ 个小于 $300$ 的素数，谁都知道要状压。
看到问题, $\varphi(\prod_{i = l}^{r} a_{i})$ ，里面那一坨就是一区间求积，知道 $\varphi(m) = m \prod_{p \mid m} \frac{p - 1}{p}$ ，然后 $p$ 被卡死在 $30$ 以内，只有 $62$ 种取值。把两块拆开就变成了维护区间积和区间积的素因数集合，后者状压维护即可。

---

本来今天还做了几道题，但是都是 $1700 - 1800$ 的屑题， 感觉没啥好写的。
简单总结一下今天的听的视频课，反正是去年的知识都想起来了。