====== 2020.05.24-2020.05.30 周报 ======


===== 团队训练 =====


===== 团队会议 =====


===== 个人训练 - nikkukun =====



==== 比赛 ====

=== 2020.05.26 Codeforces Round #645 (Div. 2) ===

^  题目  ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^
|  通过  |  √  |  √  |  √   |  √  |  √  |     |
|  补题  |     |     |      |     |     |     |




==== 学习总结 ====



=== 范围相同的互质对统计 ===

$$
\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$ 的拆解 ===

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

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

=== $\varphi$ 的拆解 ===

若 $(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 筛与分块点 ===

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

^值      ^1  ^2  ^3  ^4  ^5  ^6  ^7  ^8  ^9  ^10  ^
|向下取整   |10  |5  |3  |2  |2  |1  |1  |1  |1  |1  |  
|分块点    |√  |√  |√  |  |√  |  |  |  |  |√  |

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




==== 本周推荐 ====


=== ARC 092 B - Two Sequences ===

[[https://atcoder.jp/contests/arc092/tasks/arc092_b|题目链接]]

**题意**：给两个非负序列 $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}}$。这个性质可以用来统计加减法操作中的位运算结果。




===== 个人训练 - qxforever =====

本周基本没有训练
==== 比赛 ====

=== 2020.05.28 Educational Codeforces Round 88 ===

^  题目  ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^ 
|  通过  |  √  |  √  |     |     |  √  |  √  |
|  补题  |     |     |     |     |     |     |
==== 学习总结 ====

无
==== 本周推荐 ====


===  ===

无

===== 个人训练 - Potassium =====

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


==== 比赛 ====

无


==== 学习总结 ====

无


==== 本周推荐 ====

无