分类

$\color{Green}{Easy}$：一眼题。

$\color{Blue}{Median}$：经过思考可以做出来。

$\color{Yellow}{Hard}$：看完题解立马理解。

$\color{Orange}{Insane}$：看完题解经过一段时间的思考能够理解。

$\color{Red}{Supreme}$：看完题解经过长久思考才理解。

51Nod-1040 最大公约数之和 $\color{Green}{Easy}$

欧拉函数乱搞即可。

CSES-1713 Counting Divisors $\color{Green}{Easy}$

质因数分解简单题。

CSES-2182 Divisor Analysis $\color{Green}{Easy}$

比小奥简单。

CSES-1712 Exponentiation II $\color{Green}{Easy}$

欧拉定理秒了。

POJ-2478 Farey Sequence $\color{Green}{Easy}$

欧拉函数简单题。

CodeForces-914D Bash and a Tough Math Puzzle $\color{Blue}{Median}$

原题等价于最多只有一个数不是 $x$ 的倍数，势能线段树即可，单 log。

CSES-2417 Counting Coprime Pairs $\color{Green}{Easy}$

莫比乌斯反演即可。

CSES-2185 Prime Multiples $\color{Green}{Easy}$

暴力容斥即可。

HDU-4624 Endless Spin $\color{Yellow}{Hard}$

掏出传说中的 min-max 容斥公式：

$$E(max(S)) = \sum_{T \subseteq S} (-1)^{|T| + 1} E(min(T)) $$

然后就做完了

AtCoder-tokiomarine2020_e O(rand) $\color{Yellow}{Hard}$

现将所有不可能选的数筛掉，然后我们就只用考虑 $(T - S)$ 的部分了。

由于 $(T - s)$ 很小，可以容斥。

LibreOJ-2542 随机游走 $\color{Blue}{Median}$

其实是套路题。

首先肯定用 min-max 容斥转为求 min。

然后考虑待定系数法优化dp。

最后高维前缀和即可。

AtCoder-agc038_e Gachapon $\color{Red}{Supreme}$

min-max 容斥好题啊。

首先先 min-max 容斥转换为求一个状态 $T$ 的最小值。

令 $W = \sum_{i = 1}^n A_i$，则要选到一次集合内的元素我们需要操作 $\frac{W}{\sum_{i \in T} A_i}$ 次，记其为 $P$。

拆成没有一个元素被选中的概率可以得出（为方便令 $w(T) = \sum_{i \in T} a_i$，$r = \sum_{i \in T} B_i$）：

$$\sum_{k = 0}^r P \times k! \times \prod_{i \in T, c_1 + c_2 + \cdots + c_{|T|} = k, c_i < b_i} \frac{A_i^{c_i}}{w(T)^{c_i} \times c_i!} $$

考虑 dp，能够发现我们只需记录 $w(T)$ 和 $k$ 就可以了。

令 $f_{i, j, k}$ 表示考虑选了前 $i$ 个数，$\sum c_i = k$，$W(T) = j$ 的对答案的贡献。

可以得出状态转移方程：

$$f_{i, j, k} = f_{i - 1, j, k} - \sum_{l = 0}^{min(B_i, k)} f_{i - 1, j - A_i, k - l} \times \frac{A_i^l}{l!} $$

时间复杂度 $O(n^3)$（假设 $n$，$\sum A_i$，$\sum B_i$ 同阶）。

黑暗爆炸-2839 集合计数 $\color{Green}{Easy}$

还是简单二项式反演。

UVA-11526 H(n) $\color{Green}{Easy}$

还是简单数论分块。