两边对照一下，我们取 $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$ 秒，肯定没问题了。

代码

cf628.md 4.8 KB 履歴 Raw

Codeforces Round #628

A. EhAb AnD gCd

问题重述

题解

B. CopyCopyCopyCopyCopy

问题重述

题解

C. Ehab and Path-etic MEXs

问题重述

题解

D. Ehab the Xorcist

问题重述

题解

E. Ehab's REAL Number Theory Problem

问题重述

题解

cf628.md 4.8 KB

履歴 Raw