菜鸡 fa_555 会把一些动态简要地记在这里。主要还是留给自己以后看的。

所有代码不保证包括无关紧要的部分

---

临近省选，不会记太多的东西。

---

YY的GCD

problem

给定 $n, m \ (1 \le n, m \le 10^7)$，求 $1 \le x \le n, 1 \le y \le m$ 且 $\gcd(x, y)$ 为质数的 $(x, y)$ 有多少对。$T \ (1 \le T \le 10^4)$ 组数据。

solution

不妨设 $n \le m$。设 $t = pd$。

$$\begin{aligned} & \sum_{i = 1}^n{ \sum_{j = 1}^n{[ \gcd(i, j) \in \mathbb P]}} \\ =& \sum_{p \in \mathbb P}{ \sum_{i = 1}^n{ \sum_{j = 1}^n{[ \gcd(i, j) = p]}}} \\ =& \sum_{p \in \mathbb P}{ \sum_{i = 1}{ \lfloor n / p \rfloor}{ \sum_{j = 1}{ \lfloor m / p \rfloor}{[ \gcd(i, j) = 1]}}} \\ =& \sum_{p \in \mathbb P}{ \sum_{i = 1}{ \lfloor n / p \rfloor}{ \sum_{j = 1}{ \lfloor m / p \rfloor}{ \sum_{d \mid \gcd(i, j)}{ \mu(d)}}}} \\ =& \sum_{p \in \mathbb P}{ \sum_{d = 1}{ \lfloor n / p \rfloor}{ \mu(d) \left \lfloor \frac n{pd} \right \rfloor \left \lfloor \frac m{pd} \right \rfloor}} \\ =& \sum_{p \in \mathbb P}{ \sum_{d = 1}{ \lfloor n / p \rfloor}{ \mu(d) \left \lfloor \frac nt \right \rfloor \left \lfloor \frac mt \right \rfloor}} \\ =& \sum_{t = 1}^n{ \left \lfloor \frac nt \right \rfloor \left \lfloor \frac mt \right \rfloor \sum_{p \in \mathbb P, p \mid t}{ \mu \left( \frac tp \right)}}\end{aligned}$$

设 $f(x) = \sum_{p \in \mathbb P, p \mid t}{ \mu(t / p)}$，则 $f(x)$ 可以用埃筛在 $O(n \log \log n)$ 的时间内筛出，答案可以数论分块单次 $O( \sqrt n)$ 询问。

code

---

无平方因子数

problem

求小于等于 $n$ 的无平方因子数的个数，即求 $\sum_{i = 1}^n{ \mu^2(i)}$。

solution

考虑一个素数 $p$，那么 $p^2$ 的倍数都有平方因子，个数是 $\lfloor n / p^2 \rfloor$，应该从答案中去掉。

但是这样又多去掉了一些数。比如对于不同的素数 $p_1, p_2$，$p_1^2 p_2^2$ 就被去掉了两次，个数是 $\lfloor n / (p_1^2 p_2^2) \rfloor$，应该加回来。显然这就是容斥原理。

如果 $d$ 是 $s$ 个不同素数的乘积，那么其对答案的贡献是 $(-1)^s \lfloor n / d^2 \rfloor$；如果 $d$ 不是不同素数的乘积，即 $d$ 有平方因子，那么 $d$ 对答案没有贡献。

容斥的系数恰好是 Mobius 函数。因此答案就是

$$\sum_{i = 1}^n{ \mu^2(i)} = \sum_{d = 1}^\sqrt n{ \mu(d) \left \lfloor \frac n{d^2} \right \rfloor}$$

事实上，Mobius 反演本身就可以看成是对整除关系的容斥。

---

[SDOI2014]数表

solution

不妨设 $n \le m$。设 $t = dg$。

$$\begin{align} & \sum_{i = 1}^n{ \sum_{j = 1}^m{ \sigma( \gcd(i, j))}} \\ =& \sum_{d = 1}^n{ \sigma(d) \sum_{i = 1}^{ \lfloor n / d \rfloor}{ \sum_{j = 1}^{ \lfloor m / d \rfloor}{[ \gcd(i, j) = 1]}}} \\ =& \sum_{d = 1}^n{ \sigma(d) \sum_{i = 1}^{ \lfloor n / d \rfloor}{ \sum_{j = 1}^{ \lfloor m / d \rfloor}{ \sum_{g \mid \gcd(i, j)}{ \mu(g)}}}} \\ =& \sum_{d = 1}^n{ \sigma(d) \sum_{g = 1}^{ \lfloor n / d \rfloor}{ \mu(g) \left \lfloor \frac n{dg} \right \rfloor \left \lfloor \frac m{dg} \right \rfloor}} \\ =& \sum_{t = 1}^n{ \left \lfloor \frac nt \right \rfloor \left \lfloor \frac mt \right \rfloor \sum_{d | T}{ \sigma(d) \mu \left( \frac td \right)}} \end{align}$$

如果没有 $a$ 的限制这题就做完了。

设 $f(t) = \sum_{d | T}{ \sigma(d) \mu(t / d)}$，则当 $\sigma(d) \le a$ 时才会对 $f$ 产生贡献。

将询问离线，按 $a$ 升序排序。每次加入会对 $f$ 产生影响的 $\sigma(d)$。

用树状数组维护 $f$，每次暴力加入所有 $\sigma(d) \le a$ 的 $d$，即令所有满足 $kd \le n$ 的 $f(kd)$ 增加 $\sigma(d) \mu(k)$。

预处理 $O(n)$，修改 $O(n \log^2 n)$，查询单次 $O( \sqrt n \log n)$。

code

---

[SDOI2014]重建

problem

$n \ (1 \le n \le 50)$ 个点，若干条边，每条边有一定几率保留，求保留一棵树的概率。

solution

考虑 Matrix-Tree 定理的实质：

枚举所有生成树 $T$ 和其中的边 $e$，求

$$\sum_T{ \prod_{e \in T}{p_e}}$$

其中 $p$ 可以看做边权或出现概率，因此 $p_e = 1$。

而本题要求的是

$$\begin{align} & \sum_T{ \left( \prod_{e \in T}{p_e} \prod_{e \not \in T}{(1 - p_e)} \right)} \\ =& \sum_T{ \left( \prod_{e \in T}{p_e} \times \frac{ \prod_e{(1 - p_e)}}{ \prod_{e \in T}{(1 - p_e)}} \right)} \\ =& \prod_e{(1 - p_e) \left( \sum_T{ \prod_{e \in T}{ \frac{p_e}{1 - p_e}}} \right)} \end{align}$$

把边权设为 $p_e / (1 - p_e)$ 即可。特别地，若 $p_e = 1$，令 $p_e = 1 - \epsilon$ 来避免零作除数。

code