+++
date = "2020-03-15T21:15:00+08:00"
draft = false
tags = []
title = "Codeforces Round #628 (Div. 2)"
authors = ["xry111"]
+++

# [Codeforces Round #628](https://codeforces.com/contest/1325)

## [A. EhAb AnD gCd](https://codeforces.com/contest/1325/problem/A)

### 问题重述

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

### 题解

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

[代码](https://codeforces.com/contest/1325/submission/73300346)

## [B. CopyCopyCopyCopyCopy](https://codeforces.com/contest/1325/problem/B)

### 问题重述

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

### 题解

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

[代码](https://codeforces.com/contest/1325/submission/73300691)

## [C. Ehab and Path-etic MEXs](https://codeforces.com/contest/1325/problem/C)

### 问题重述

给你一个树 $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|$。

[代码](https://codeforces.com/contest/1325/submission/73321338)

## [D. Ehab the Xorcist](https://codeforces.com/contest/1325/problem/D)

### 问题重述

给定非负整数 $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$ 的数列。

[代码](https://codeforces.com/contest/1325/submission/73304531)

## [E. Ehab's REAL Number Theory Problem](https://codeforces.com/contest/1325/problem/E)

### 问题重述

给定一个正整数组成的数列 $\\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$ 秒，肯定没问题了。

[代码](https://codeforces.com/contest/1325/submission/73333120)