耶。
2021 CCPC 网络赛 重赛 1005 Monopoly
大富翁棋盘，一圈一共 $n$ 个数 $a$，代表走到此格时获得的分数（可以是负数）。初始分数为 $0$，从第一个格子开始走，一次走一格。给定 $m$ 次询问 $x$，输出最少几步恰好能获得 $x$ 分，不能则输出 $-1$。走 $0$ 步即可得到 $0$ 分。
$1\le T \le 20, 1\le n, m\le 10^5, -10^9\le a_i\le 10^9, -10^{12}\le x\le 10^{12}, \sum n \le 5\times 10^5, \sum m \le 5\times 10^5$
类似 CF 上的这道题，都需要把整体的前缀和作为走一趟下来的变化量。
有了前缀和 $p_i$，我们的问题就变成了：针对每个询问 $x$，在 $p$ 里寻找下标 $i$，使
- $p_i + k\cdot p_n = x, k\in N$
- $i + k \cdot n$ 最小
显然符合条件的 $p_i$ 必须与 $x$ 对变化量同余。如果变化量为正，我们需要找到不大于 $x$ 的最大 $p_i$，多个符合条件的 $p_i$ 中取最小下标；如果变化量为负，将所有的 $p_i$ 以及 $x$ 变号，转化处理；变化量为 $0$ 时，在 $p_i$ 里找第一个出现的 $x$ 即可。注意，因为存在负数，取余的时候需要修正到正数。
于是我们可以把所有的 $p_i$ 都对变化量取余，结果相同的下标存在一起，其中如果有多个 $p_i$ 值相同，只有最小下标是我们需要的。这是一个 map 套 map，由余数可以查到所有的 $p_i$ 值，由 $p_i$ 值又可以查到第一次出现位置。最后用 map 的 lower_bound 就能做了。不用哈希的话复杂度 $O(n\log^2 n)$。
要特别注意的地方是在 map 里面查找的方式。如果直接用它重载过的下标去看有没有存值，会让 map 新建值容器，可能炸空间。另外，记下所有的 $p_i$ 位置不会炸空间，但是后面为二分做排序时要枚举 map 里面已经存好的键值对，枚举所有余数会超时，同时二分之后的逻辑也比较麻烦，一定要考虑全。
牛客 19483 B 智乃酱的子集与超集
定义一个集合的价值为其所有元素的异或和。长度为 $N$ 的一列数 $a$, 给定一组下标，表示数列的一个子集 $U$，输出 $U$ 所有子集的价值之和，以及所有超集的价值之和。全集为数列 $a$。
$1\le N\le 20, 1\le M\le 10^5, 1\le a_i\le 10^6$
只是记一个比较巧的东西。
二进制枚举所有可能的组合，对于一种组合 $j$ 枚举每个位，算出它这个集合的价值。
现在我们有各个子集的价值了，接着做子集或者超集价值和。以子集为例，枚举每个下标，对于一个下标 $i$，枚举所有组合的第 $i$ 位，如果为 $1$，则这一位变成 $0$ 可以得到一个子集，那么加上它。虽然加上的下标只去掉了一个元素，但是其中的内容已经包含了前几个元素去掉和没去掉的所有组合。
CF 1459 C Row GCD
两个正整数序列 $a_i$，$b_j$，分别长 $n$ 和 $m$。对于每个 $j\in [1, m]$，输出 $a_1 + b_j, a_2 + b_j, \cdots , a_n + b_j$ 的最大公因数。
$1\le n, m\le 2\times 10^5, 1\le a_i, b_j\le 10^{18}$
这里需要一个从辗转相除法看出的结论：
从后面的所有项里减去第一项，结论不变，但是不再需要考虑 $b_j$ 和 $a_i$ 的组合。预处理一下然后对于每个 $a_1 - b_j$ 做一次 $\gcd$ 即可。
CF 1398 C Good Subarrays
只有 $0$ 到 $9$ 的数列 $a_i$，找出所有的数对 $(l, r)(l\le r)$，使得 $\sum_l^r a_i = r - l + 1$。求数对数量。
$1\le t\le 1000, 1\le n \le 10^5, \sum n \le 10^5$
对原来的式子变形：
于是我们只需要寻找两个下标 $i$，$j$，$presum_i - i = presum_j - j$。注意 $i < j$，因为 $r$ 与 $l$ 可能相等。
做完前缀和之后处理一下，用 map 对相同差计数，算一下就好了。
CF 1349 A Orac and LCM
一个数列 $a_i$，求出其中所有数对最小公倍数的最大公约数，即 $gcd({lcm(a_i, a_j) | i < j})$。
$2\le n\le 10^5, 1\le a_i\le 2\times 10^5$
固定 $i$ 去枚举所有的 $j$，得到 $n - i$ 个数对，那么只要快速算出 $\gcd (\mathrm{lcm} (ai, a{i + 1}), \mathrm{lcm} (ai, a{i + 2}), \cdots, \mathrm{lcm} (ai, a{n}))$，然后对于每个 $i$，把算出的 gcd 一起求一个 gcd 就是答案。
这里用到一套结论性的东西，就是 $\gcd$ 和 $\mathrm{lcm}$ 的分配律：
这个可以从数论角度证明，但是这个知乎回答好像有点问题。可以分解质因数再从幂次上去证，比较丑。应该也能从代数系统证，和 $\max$、$\min$ 应该是“同构”的。加引号是因为较大较小操作都不是群，没有逆元。
那就把
化成了
然后就很好做了。结论题。