CF2126E.G-C-D, Unlucky!

给定两个长度为 $n$ 的数组 $p$ 和 $s$，其中 $p$ 是某个数组 $a$ 的前缀最大公约数（GCD），$s$ 是同一个数组 $a$ 的后缀最大公约数。换句话说，如果数组 $a$ 存在，则对于每个 $1 \le i \le n$，都有：

• $p_i = \gcd(a_1, a_2, \dots, a_i)$
• $s_i = \gcd(a_i, a_{i+1}, \dots, a_n)$

请判断是否存在这样的数组 $a$，使得给定的 $p$ 和 $s$ 可以由它得到。

$^\ast$ $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例包含三行：

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示数组的长度。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \leq p_i \le 10^9$），表示数组 $p$ 的元素。

第三行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$（$1 \leq s_i \le 10^9$），表示数组 $s$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，如果存在数组 $a$ 使得给定的 $p$ 和 $s$ 可以由它得到，输出 "Yes"；否则输出 "No"。输出时不区分大小写（如 "yEs"、"yes"、"Yes"、"YES" 都可以）。

对于第一个测试用例，一个可能的数组为：[ 72,\ 24,\ 3,\ 6,\ 12,\ 144 ]。

对于第二个测试用例，可以证明不存在这样的数组。

对于第三个测试用例，存在一个数组：[ 125,\ 125,\ 125,\ 25,\ 75 ]。

由 ChatGPT 4.1 翻译