差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:i_dont_know_png:week_summary_4 [2020/05/23 20:17]
potassium 创建
+++ 2020-2021:teams:i_dont_know_png:week_summary_4 [2020/05/31 13:39] (当前版本)
qxforever [本周推荐]
@@ 行 9: / 行 9: @@
 ===== 个人训练 - 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]
+$$
-===== 个人训练 - qxforever =====
+这个比较显然，因为存在平方因子就是 $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)$ 当前缀和。
-==== 学习总结 ====
@@ 行 39: / 行 79: @@
-===  ===
+=== ARC 092 B - Two Sequences ===
-[[|题目链接]]
+[[https://atcoder.jp/contests/arc092/tasks/arc092_b|题目链接]]
-===== 个人训练 - Potassium =====
+**题意**：给两个非负序列 $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  ^
+|  通过  |  √  |  √  |     |     |  √  |  √  |
+|  补题  |     |     |     |     |     |     |
 ==== 学习总结 ====
+无
 ==== 本周推荐 ====
@@ 行 57: / 行 114: @@
 ===  ===
-[[|题目链接]]
+无
-**题意**：
+===== 个人训练 - Potassium =====
+本周进入考期，暂停训练。
+==== 比赛 ====
+无
+==== 学习总结 ====
+无
+==== 本周推荐 ====
-**题解**：
+无

CVBB ACM Team

用户工具

站点工具

差别

页面工具