A16654. No Cost Too Great (Easy Version)
编程题
普及/提高-
知识点
题目描述
这是该问题的简单版本。与困难版本的区别在于，本题中 $b_i = 1$ 对于所有 $i$（$1 \le i \le n$）。只有当你解决了所有版本才能进行“hack”。
你有两个长度均为 $n$ 的正整数数组 $a$ 和 $b$。你可以进行以下操作任意次（也可以一次都不做）：
- 选择一个整数 $i$（$1 \le i \le n$），将 $a_i$ 增加 $1$，花费为 $b_i$。
请你求出使得存在两个整数 $i, j$（$1 \le i < j \le n$），满足 $\gcd(a_i, a_j) > 1$ 的最小总花费。
$\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数，详见[最大公约数](https://en.wikipedia.org/wiki/Greatest_common_divisor)。
你有两个长度均为 $n$ 的正整数数组 $a$ 和 $b$。你可以进行以下操作任意次（也可以一次都不做）：
- 选择一个整数 $i$（$1 \le i \le n$），将 $a_i$ 增加 $1$，花费为 $b_i$。
请你求出使得存在两个整数 $i, j$（$1 \le i < j \le n$），满足 $\gcd(a_i, a_j) > 1$ 的最小总花费。
$\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数，详见[最大公约数](https://en.wikipedia.org/wiki/Greatest_common_divisor)。
输入格式
每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 2 \cdot 10^5$）。
第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$，其中 $\color{red}{b_i = 1}$。
所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 2 \cdot 10^5$）。
第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$，其中 $\color{red}{b_i = 1}$。
所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
输出格式
对于每组测试用例，输出最小花费。
输入输出样例
输入 #1
6 2 1 1 1 1 2 4 8 1 1 5 1 1 727 1 1 1 1 1 1 1 2 3 11 1 1 3 2 7 11 1 1 1 3 7 12 13 1 1 1
输出 #1
2 0 2 1 1 1
说明/提示
在第一个测试用例中，可以如下操作：$[\color{red}1, 1] \xrightarrow{x = 1} [2, \color{red}1] \xrightarrow{x = 2} [2, 2]$。此时 $\gcd(a_1, a_2) = \gcd(2, 2) = 2$，因此 $\gcd(a_1, a_2) > 1$。可证明这是最小的花费。
在第二个测试用例中，本来就已经有 $\gcd(a_1, a_2) = 4$，因此无须进行任何操作。
在第二个测试用例中，本来就已经有 $\gcd(a_1, a_2) = 4$，因此无须进行任何操作。