CF2210C2 A Simple GCD Problem (Hard Version)

这是本题的困难版本。不同版本之间的区别在于，本版本中 $1 \leq n \leq 5 \cdot 10^{4}$，$1 \leq b_i \leq 10^{9}$ 对于 $1 \leq i \leq n$，并且时间限制为 $6$ 秒。请注意，一个版本的解法并不一定适用于另一个版本。只有在你解决了所有版本后才能 hack 本题。 你获得了长度为 $n$ 的两个数组 $a$ 和 $b$。 对于数组 $a$ 的每个下标 $i$（$1 \leq i \leq n$），你可以对 $a_i$ 至多执行一次如下操作： - 选择一个任意整数 $m$（$\mathbf{m \neq a_i}$），满足 $1 \leq m \leq b_i$，然后设置 $a_i := m$。 记执行所有操作后的数组为 $a'$。你只能在满足下列条件的情况进行操作： - 对所有 $1 \leq l < r \leq n$，都有 $\operatorname{gcd}(a_l, a_{l+1}, \ldots, a_r) = \operatorname{gcd}(a'_l, a'_{l+1}, \ldots, a'_r)$。 其中，$\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的[最大公约数（GCD）](https://en.wikipedia.org/wiki/Greatest_common_divisor)。 你需要确定在保证上述条件依然成立的情况下，最多可以执行多少个操作。

每个测试包含多组测试用例。第一行为测试用例数 $t$（$1 \le t \le 10^4$）。接下来的描述为每组测试数据。 每组测试数据的第一行包含一个整数 $n$（$2 \leq n \leq 5\cdot 10^4$）——数组 $a$ 的长度。 每组测试数据的第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）。 每组测试数据的第三行包含 $n$ 个用空格分隔的整数 $b_1, b_2, \ldots, b_n$（$1 \le b_i \le 10^9$）。 保证所有测试数据中 $n$ 的总和不超过 $5\cdot 10^4$。

对于每组测试数据，输出最多可以执行多少次操作。

在第一个测试用例中，由于所有子数组的 $\gcd$ 都是 $1$，所以可以把数组变成 $a' = [67, 5, 7, 11, 1, 2, 1]$。这样我们对数组中 $7$ 个元素都做了一次操作，且这是最多的情况。 在第二个测试用例中，可以把数组变成 $a' = [938, 2613, 4489]$。可以证明，经过这样的操作后所有子数组的 $\gcd$ 都保持不变。因此答案为 $3$。 在第三个测试用例中，可以证明不能进行任何操作，所以答案是 $0$。 由 ChatGPT 5 翻译