杜教筛

没交 $\text{score：NULL rk：NULL}$ Problem A：区间第k小题面 题解先考虑离线，整体二分，二分答案 $mid$，处理所有 $\le mid$ 的数，那么此时问题就转化为在区间出现次数不超过 $w$ 的数有多少个 不妨关注每个数对询问区间 $[L, R]$ 的贡献，对某个数 $a$，若它是从左往右后 $w$ 个出现为 $a$ 的数，则它的贡献为 $1$，若为倒数第 $w + 1$ 个则贡献为 $- w$，剩下的贡献都为 $0$，那么我们就可以开一个队列，首先总大小（即不删去超过 $w$ 的）算出来，此时计算需要删去的，队列大小未到 $w$ 时没有需要删的，若大于 $w$ 时每次就让队首点贡献减去 $w + 1$，当然之前多减的还要加回来 那么现在就可以考虑从离线转成在线，在整体二分的过程中每一层（即每一次二分的 $[l, r]$）都会建一些可持久化线段树，而它又最多会修改 $O (n \log n)$ 次，开 $O (n \log^2 n)$ 个节点，所以把每一层的可持久化线段树都存下来，在线二分时即可直接查找，总时间复杂度 $O ...

根据Crash的数字表格，很容易可以将式子化简为$$\begin{aligned} Ans &= \sum\limits_{i = 1}^n \sum\limits_{j = 1} ij(i, j) \\ &= \sum\limits_{d = 1}^n d^3 \sum\limits_{k = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} \mu(k) k^2 \left( \sum\limits_{i = 1}^{\left\lfloor\frac{n}{kd}\right\rfloor} i \right)^2 \end{aligned}$$感觉 $d, k$ 放在一起式子无法继续化简，主要是有 $kd$ 存在，故令 $T = kd$ ，则有$$Ans = \sum\limits_{T = 1}^n \left( \sum\limits_{i = 1}^{\left\lfloor\frac{n}{T}\right\rfloor} i \right)^2 T^2 \sum\limits_{d | T} d \mu(\frac{T ...

前置相关 类型积性函数（注：以下皆为完全积性函数，即无需满足 $x \perp y$ 即有 $f(x) · f(y) = f(xy)$ $\epsilon (n) = [n = 1]$ $id (n) = n$ 狄利克雷卷积与莫比乌斯函数 狄利克雷卷积与欧拉函数 此处若以 $id $ 作单位元，则 $1$ 为 $\phi$ 的逆，即 $\phi * 1 = id$ 证明：由 $\sum\limits_{d | n} \phi (d) = n$ ，再带回原式可证 莫比乌斯函数与欧拉函数的转化$$\begin{aligned} \phi * 1 &= id \ \phi * 1 * \mu &= id * \mu \ \phi * \epsilon &= id * \mu \ \phi &= \sum\limits_{d | n} \mu(d) \frac{n}{d} \ \frac{\phi}{n} &= \sum\limits_{d | n} \frac{\mu(d)}{d} \end{aligned}$$ 杜教筛 杜教筛用于求解积性函 ...

题意求解 $1 \le x \le n, ~ 1 \le y \le m$ 中满足在 $k$ 进制下 $\frac{x}{y}$ 是有限循环小数的个数 题解很好然后我一开始在计算器上敲了半个小时然后由于眼瞎并且归纳能力差并没有发现规律 设 $\frac{x}{y}$ 的循环节长度为 $l$，则有$$\begin{aligned}\frac{xk^l}{y} - \left\lfloor\frac{xk^l}{y}\right\rfloor &= \frac{x}{y} - \left\lfloor\frac{x}{y}\right\rfloor \\xk^l - \left\lfloor\frac{xk^l}{y}\right\rfloor y &= x - \left\lfloor\frac{x}{y}\right\rfloor y \\xk^l &\equiv x \pmod y \\k &\equiv 1 \pmod y\end{aligned}$$也就是说只要满足 $y \bot k$ 即可满足题意，故可将问题化为$$\begin{aligned ...