莫比乌斯反演

没交 $\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 ...

概念引入数论函数　　　　指定义域为正整数的函数　　　　定义其加法为逐项相加，即$(f + g)(n) = f(n) + g(n)$　　　　定义其数乘为逐项相乘，即$(xf)(n) = x × f(n)$ 单位元　　　　单位元是集合中一种特别的元素，当单位元与其它元素相结合时，不会改变其它元素的值 逆元　　　　逆元是指可以取消另一给定元素运算的元素，即将其变回单位元 符号表示　　　　$[A]$表示条件$A$是否为真　　　　此处的符号”$*$”表示狄利克雷卷积 狄利克雷卷积　　令$t(n) = f(n) * g(n)$，则 　　 $$t(n) = \sum\limits_{i | n} f(i)g(\frac{n}{i})$$ 　　那么狄利克雷卷积显然有下面几个性质： 满足乘法交换律、结合律、分配律 对于单位元$\epsilon(n) = [n = 1]$，满足$\epsilon(n)*f(n) = f(n)$　　　　- 对于每一个$f(1) \ne 1$的数论函数$f(n)$，皆存在其逆元$f^{- 1}(n)$，满足$f(n) * f^{- 1}(n) = \epsilon(n)$，那 ...

根据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 ...

题意求 $\sum\limits_{i = 1}^N \sum\limits_{j = 1}^M lcm (i, j)$ Solution易知，原式$$\sum\limits_{i = 1}^N \sum\limits_{j = 1}^M \frac{ij}{\gcd (i, j)}$$枚举 $\gcd (i, j)$ ，且将 $d$ 提出来得$$\sum\limits_{d = 1}^{\min (N, M)} d \sum\limits_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor} \sum\limits_{j = 1}^{\left\lfloor\frac{M}{d}\right\rfloor} ij[(i, j) = 1]$$将公式 $\sum\limits_{k | n} \mu(k) = [n = 1]$ 代入，得$$\sum\limits_{d = 1}^{\min (N, M)} d \sum\limits_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor} \sum\limits ...

题意求解 $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 ...