CF2210C1 A Simple GCD Problem (Easy Version)

这是该题目的简单版。不同之处在于本题满足 $1 \leq n \leq 2 \cdot 10^{5}$，且 $b_i = a_i$（$1 \leq i \leq n$）。请注意，一个版本的解法不一定能解决另一个版本。只有先通过所有版本，才能对本题进行 Hack。 你有两个长度为 $n$ 的数组 $a$ 和 $b$。 对于数组 $a$ 的每一个下标 $i$（$1 \leq i \leq n$），你最多可以对其执行一次如下操作： - 任选一个整数 $m$（$\mathbf{m \neq a_i}$），满足 $1 \leq m \leq b_i$，并将 $a_i$ 赋值为 $m$。 记所有操作后得到的数组为 $a'$。你只能在保证以下条件成立的情况下进行上述操作： - 对任意 $1\leq l

每个测试包含若干组用例。第一行输入测试用例数 $t$（$1 \le t \le 10^4$）。接下来依次给出各组测试用例。 每组用例的第一行输入一个整数 $n$（$2 \leq n \leq 2\cdot 10^5$），表示数组 $a$ 的长度。 第二行输入 $n$ 个空格分隔的整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）。 第三行输入 $n$ 个空格分隔的整数 $b_1, b_2, \ldots, b_n$（$\color{red}{b_i = a_i}$）。 保证所有测试用例中 $n$ 之和不超过 $2\cdot10^5$。

对于每组测试用例，输出一行表示最多可以进行的操作次数。

对于第一组用例，所有子数组的 GCD 均为 $1$。因此，可以进行 $6$ 次操作，将数组变为 $a' = [1, 1, 1, 1, 1, 1, 1]$。可以证明本例子最多能进行 $6$ 次操作。 对于第二组用例，注意所有值都相等，减少任意值都会导致子数组的 GCD 降低。因此，操作数为 $0$。 对于第三组用例，可以证明最多可以进行 $2$ 次操作。 由 ChatGPT 5 翻译