$$ \sum _{i=1} ^n \sum _{j=1} ^n [(i, j)=1] = 2\sum _{i=1}^n \varphi(i) - 1 $$

两两互质个数减去 $(1, 1)$ 的情况。也可以写成

$$ \sum _{i=1} ^n \sum _{j=1} ^n [(i, j)=1] = \sum _{d=1}^n \mu(d) \left\lfloor \frac nd \right\rfloor ^2 $$

$$ \mu(ab) = \mu(a) \mu(b) [(a, b) = 1] $$

这个比较显然，因为存在平方因子就是 $0$ 了。

若 $(a, p) = 1$，则

$$ \varphi(ap^k) = \varphi(a) \cdot \varphi(p) \cdot p^{k-1} $$

这说明对 $k > 1$ 的质因数 $p$，它都可以直接丢出来。换句话说，如果 $n = \prod p_i^{k_i}$，令 $x = \prod p_i,\ y = \prod p_i^{k_i-1}$，则

$$ \varphi(n) = \varphi(xy) = \varphi(x) \cdot y $$

暂时不知道可以做什么。

min_25 筛中，分块的方案是这样的（令 $n = 10$）：

即是说，分块点是向下取整的值相同时，能取到的最大值。所以在两个分块点 $(a, b]$ 的部分就是一块，可以直接用 $f(b) - f(a)$ 当前缀和。

题目链接

题意：给两个非负序列 $a_1, a_2, \ldots, a_n$ 和 $b_1, b_2, \ldots, b_n$，求所有 $a_i + b_j$（可重复）的异或和。

$n \in [1, 2 \times 10^5]$，数组元素在 $[0, 2^{28}]$ 内。

题解：显然可以按位考虑贡献。如果我们固定了一个 $a$ 和二进制中的某一位 $k$，相当于考虑有多少个 $b_i$，满足 $a + b_i$ 的第 $k$ 位是 $1$。

这个东西就很好玩了：如果给所有 $a + b_i$ 模 $2 \cdot 2 ^{k-1}$，则余数落在 $[2^{k-1},\ 2 \cdot 2^{k-1})$ 之间的数都是满足要求的。

归纳一下，二进制表示中 $x$ 的第 $k$ 位为 $1$ 的充要条件是，$x \in [2^{k-1},\ 2 \cdot 2^{k-1}) \pmod {2 \cdot 2 ^{k-1}}$。这个性质可以用来统计加减法操作中的位运算结果。

本周基本没有训练

无

无

本周进入考期，暂停训练。

无

无

无