Codeforces Round #628

A. EhAb AnD gCd

问题重述

给你数 $x$，让你求 $a, b$ 使得 $GCD(a, b) + LCM(a, b) = x$。

题解

假题，只要选择 $a = x-1, b = 1$ 即可。

代码

B. CopyCopyCopyCopyCopy

问题重述

给你一个数列 $\mathbf{a} = \{a_i\}$， 把它重复 $n$ 次以后得到一个新的数列， 求新的数列的最长严格上升子序列的长度。

题解

假题，我们在第 $k$ 次重复中选择 $\mathbf{a}$ 中第 $k$ 小的元素。 如果所有元素都相同，那么就能选出 $n$ 个。如果有重复的，相同的数只能选一次， 因此答案就是 $\mathbf{a}$ 中不同元素的个数。

代码

C. Ehab and Path-etic MEXs

问题重述

给你一个树 $G = (V, E)$，让你给出一个双射 $f: E \rightarrow \{0, \cdots, |E|-1\}$，使得

$$\max_{u, v} MEX(\{f(x) | x \in PATH(u, v)\})$$

最小。$PATH(u, v)$ 是 $u$ 到 $v$ 路径上的所有边的集合， $MEX$ 就是博弈论里的那个东西; $$MEX(S) = \min (\mathbb{N} \setminus S)$$

题解

如果有 $3$ 个叶子节点 $u, v, w$，我们把 $0, 1, 2$ 直接分别指定给连接这 $3$ 个叶子节点的边，可以看出此时答案一定是 $2$，不可能有更小的答案。 如果只有 $2$ 个叶子节点，树就退化成一条链，此时无论怎么指定， 答案都是 $|E|$。

代码

D. Ehab the Xorcist

问题重述

给定非负整数 $u$ 和 $v$，求一个尽量短的数列 $\mathbf{a}$， 使得其中所有数异或起来为 $u$，和为 $v$。

题解

首先如果 $u > v$ 或者 $u$ 和 $v$ 奇偶不同，显然无解。

根据计算二进制和的进位法，容易看出 $$(a \oplus b) + (a \cup b) + (a \cup b) = a + b$$

根据异或的计算法则，有 $$(a \oplus b) \oplus (a \cup b) \oplus (a \cup b) = a \oplus b$$

两边对照一下，我们取 $p = u, q = r = (v-u)/2$，则 $\{p,q,r\}$ 就是一个合法的答案。可见答案的长度最长就是 $3$。 有一些特殊情况下答案可能更短：如果 $u = v = 0$，则答案是空数列。 如果 $u = v > 0$，则答案就是一个包含 $u$ 的长度为 $1$ 的数列。 如果 $p \oplus q = p + q$，则我们可以将它们合并起来， 得到长度为 $2$ 的数列。

代码

E. Ehab’s REAL Number Theory Problem

问题重述

给定一个正整数组成的数列 $\mathbf{a} = \{a_i\}$，从中选出尽量少的数， 使得它们的乘积是完全平方数。保证 $|\mathbf{a}| \leq 10^5$， $a_i \leq 10^6$，且 $a_i$ 至多有 $7$ 个因子。

题解

$a_i$ 至多有 $7$ 个因子，说明其至多有 $2$ 个不同的质因子 ($3$ 个不同质数乘来乘去就能得到 $8$ 个不同的数了)。 对于每个质因子我们只关心它在 $a_i$ 中出现次数的奇偶性。 如果某个 $a_i$ 本身就是完全平方数，那么只选它就行了。 否则，$a_i$ 要么有 $1$ 个出现奇数次的质因子， 要么有 $2$ 个出现奇数次的质因子。我们将所有质数和 $1$ 作为点建个图， 对于第一种情况，把这个质因子和 $1$ 连起来；对于第二种情况， 把两个质因子连起来。然后容易看出，图中的每个环都是一个合法的答案， 我们要找的就是最小环。BFS 找最小环的时间复杂度是 $\mathcal{O}(|V||E|)$： 每次 BFS 需要 $\mathcal{O}(|E|)$ 的时间，需要对于 $|V|$ 个点都作为起点 BFS 一次，这样会超时。但是本题中如果大于 $\sqrt{\max a_i}$ 的点在某个环中，则它连接到的必然都是小于 $\sqrt{\max a_i}$ 的点。 因此，我们不需要考虑以大于 $\sqrt{\max a_i}$ 的点作为起点的情况 (这样的环一定也包含小于 $\sqrt{\max a_i}$ 的点， 以这个较小的点做起点就能找到这个环了)。这样就只要枚举 $\mathcal{O}(\sqrt{\max a_i} / \log \max a_i)$ 个起点， 边数 $|E|$ 是 $\mathcal{O}(|\mathbf{a}|)$ 的，因此总的时间复杂度是 $$\mathcal{O}(\frac{\sqrt{\max a_i} |\mathbf{a}|}{\log \max a_i})$$ 大概算一下也就是不到 $10^8$ 量级，这题时限还是 $3$ 秒，肯定没问题了。

代码