← 返回题目列表

Codeforces · 2126/E

E. G-C-D,倒霉!

中文机器翻译题面 查看原题

给出两个长度为 $$$n$$$ 的数组 $$$p$$$ 和 $$$s$$$,其中 $$$p$$$ 是某个数组 $$$a$$$ 的前缀 GCD$$$^{\text{∗}}$$$,$$$s$$$ 是同一数组 $$$a$$$ 的后缀 GCD。换句话说,如果数组 $$$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)$$$。
判断是否存在可以获取给定数组$$$p$$$和$$$s$$$的数组$$$a$$$。

$$$^{\text{*}}$$$$$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。

输入

第一行包含一个整数 $$$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$$$) — 数组的元素。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$s_1, s_2, \dots, s_n$$$ ($$$1 \leq s_i \le 10^9$$$) — 数组的元素。

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

输出

对于每个测试用例,输出“是"(不带引号)如果存在可以获取给定数组 $$$p$$$ 和 $$$s$$$ 的数组 $$$a$$$,并且 "No"(不带引号)否则。

您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“是", "是", "是“,和”是”将被接受为肯定答案。

示例

输入
复制

5
6
72 24 3 3 3 3
3 3 3 6 12 144
3
1 2 3
4 5 6
5
125 125 125 25 25
25 25 25 25 75
4
123 421 282 251
125 1981 239 223
3
124 521 125
125 121 121

输出
复制

YES
NO
YES
NO
NO

注意

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

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

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