题目重述

给定两个长度为 $n$ 的数组 $p[1 \dots n]$ 和 $s[1 \dots n]$，它们声称是某个隐藏数组 $a[1 \dots n]$ 的前缀 GCD 和后缀 GCD：

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

判断是否存在这样的数组 $a$。

---

解题思路

1. 必要的基本条件

对于前缀 GCD 序列，我们有单调性：$p_i$ 一定是 $p_{i-1}$ 的约数，即

$$p_{i-1} \bmod p_i = 0 \quad (i \ge 2).$$

同样，后缀 GCD 序列满足

$$s_{i+1} \bmod s_i = 0 \quad (i \le n-1).$$

另外，整个数组的 GCD 必须同时等于 $p_n$ 和 $s_1$，因此

$$p_n = s_1.$$

记这个公共值为 $g$。若上述任一条件不成立，直接输出 NO。

---

2. 提取公共因子 $g$

令

$$P_i = \frac{p_i}{g}, \quad S_i = \frac{s_i}{g}.$$

则所有 $P_i, S_i$ 均为正整数，且 $P_n = S_1 = 1$。原问题等价于：是否存在数组 $A$ 使得

$$\gcd(A_1,\dots,A_i) = P_i, \quad \gcd(A_i,\dots,A_n) = S_i, $$

其中 $A_i = a_i / g$ 也是正整数。最终 $a_i = g \cdot A_i$。

---

3. 单个位置的约束

考虑位置 $i$（$2 \le i \le n-1$）。设我们已经知道：

• 前 $i-1$ 个数的 GCD 为 $P_{i-1}$，
• 后 $n-i$ 个数的 GCD 为 $S_{i+1}$。

我们需要选择 $A_i$，使得：

$$\gcd(P_{i-1}, A_i) = P_i, \quad \gcd(A_i, S_{i+1}) = S_i. $$

由于 $P_{i-1}$ 是 $P_i$ 的倍数（由前缀 GCD 性质），记

$$x = \frac{P_{i-1}}{P_i} \quad (\text{整数} \ge 1).$$

同理，$S_{i+1}$ 是 $S_i$ 的倍数，记

$$y = \frac{S_{i+1}}{S_i} \quad (\text{整数} \ge 1).$$

则条件变为：

$$\gcd(x \cdot P_i, A_i) = P_i, \quad \gcd(A_i, y \cdot S_i) = S_i. $$

将 $A_i$ 写成 $P_i \cdot S_i \cdot t$ 的形式（因为 $A_i$ 必须同时是 $P_i$ 和 $S_i$ 的倍数）。代入第一式：

$$\gcd(x \cdot P_i,\; P_i S_i t) = P_i \cdot \gcd(x,\; S_i t) = P_i \quad \Longrightarrow \quad \gcd(x, S_i t) = 1. $$

第二式：

$$\gcd(P_i S_i t,\; y S_i) = S_i \cdot \gcd(P_i t,\; y) = S_i \quad \Longrightarrow \quad \gcd(P_i t, y) = 1. $$

我们希望存在整数 $t \ge 1$ 使得这两个互质条件同时成立。

---

4. 关键观察

由于 $x = P_{i-1} / P_i$，$x$ 与 $P_i$ 互质（因为 $P_{i-1}$ 除以 $P_i$ 后剩下的因子不会出现在 $P_i$ 中）。同理，$y$ 与 $S_i$ 互质。

那么，取 $t = 1$ 即可，此时条件变为：

$$\gcd(x, S_i) = 1, \quad \gcd(P_i, y) = 1.$$

如果这两个条件成立，那么 $A_i = P_i \cdot S_i$ 就是一个合法的选择。
如果其中某个 GCD 大于 1，则无论 $t$ 取何值都无法同时满足两个互质条件（因为 $x$ 与 $P_i$ 互质，$x$ 的质因子只能靠 $S_i$ 或 $t$ 抵消，但 $S_i$ 与 $x$ 不互质时，即使 $t$ 包含 $x$ 的因子，也会破坏 $\gcd(P_i t, y)=1$ 的条件）。严格证明略，但结论是：条件 $\gcd(x, S_i)=1$ 且 $\gcd(P_i, y)=1$ 是充要的。

---

5. 边界情况

• 当 $i=1$：没有 $P_{i-1}$，只需 $\gcd(A_1, S_2) = S_1$。由于 $S_1 = 1$，所以 $\gcd(A_1, S_2)=1$。取 $A_1 = P_1 \cdot S_1 = P_1$（因为 $S_1=1$），条件自动满足（$P_1$ 与 $S_2$ 互质？需要验证）。实际上我们统一用公式 $A_i = P_i \cdot S_i$ 对 $i=1$ 也成立，但需要额外检查 $\gcd(P_1, y_1)=1$，其中 $y_1 = S_2 / S_1 = S_2$。所以边界条件也包含在后续检查中。

• 当 $i=n$：类似地，取 $A_n = P_n \cdot S_n = 1 \cdot S_n = S_n$，需要 $\gcd(x_n, S_n)=1$，其中 $x_n = P_{n-1} / P_n = P_{n-1}$。检查即可。

因此，我们只需对每个 $i$（从 $2$ 到 $n$）检查 $\gcd\big(\frac{P_{i-1}}{P_i},\; S_i\big) = 1$，以及对每个 $i$（从 $1$ 到 $n-1$）检查 $\gcd\big(P_i,\; \frac{S_{i+1}}{S_i}\big) = 1$。

---

6. 算法步骤总结

1. 验证 $p_{i-1} \bmod p_i = 0$（$i\ge 2$），$s_{i+1} \bmod s_i = 0$（$i\le n-1$），且 $p_n = s_1$。若失败，输出 NO。
2. 令 $g = p_n$，计算 $P_i = p_i / g$，$S_i = s_i / g$。
3. 对于 $i = 2$ 到 $n$：
   • 令 $x = P_{i-1} / P_i$（整数），若 $\gcd(x, S_i) \neq 1$，输出 NO。
4. 对于 $i = 1$ 到 $n-1$：
   • 令 $y = S_{i+1} / S_i$（整数），若 $\gcd(P_i, y) \neq 1$，输出 NO。
5. 全部通过则输出 YES。

若需要构造一个合法数组，可取 $a_i = g \cdot P_i \cdot S_i$。

---

7. 复杂度分析

每个测试用例 $O(n \log M)$，其中 $M$ 是数值上限（$10^9$）。所有 $n$ 总和不超过 $10^5$，因此总时间非常充裕。

---

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

void solve() {
    int n;
    cin >> n;
    vector<ll> p(n), s(n);
    for (int i = 0; i < n; ++i) cin >> p[i];
    for (int i = 0; i < n; ++i) cin >> s[i];

    // 基本整除条件
    for (int i = 1; i < n; ++i) {
        if (p[i-1] % p[i] != 0) { cout << "NO\n"; return; }
        if (s[i] % s[i-1] != 0) { cout << "NO\n"; return; }
    }
    if (p[n-1] != s[0]) { cout << "NO\n"; return; }

    ll g = p[n-1];
    vector<ll> P(n), S(n);
    for (int i = 0; i < n; ++i) {
        P[i] = p[i] / g;
        S[i] = s[i] / g;
    }

    // 检查中间条件
    for (int i = 1; i < n; ++i) {
        ll x = P[i-1] / P[i];
        if (gcd(x, S[i]) != 1) { cout << "NO\n"; return; }
    }
    for (int i = 0; i < n-1; ++i) {
        ll y = S[i+1] / S[i];
        if (gcd(P[i], y) != 1) { cout << "NO\n"; return; }
    }

    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}