A16655. No Cost Too Great (Hard Version)
编程题
普及+/提高
知识点
题目描述
这是该问题的难度较高版本。不同之处在于本版本中 $1 \le b_i \le 10^9$ 对所有 $i$ ($1 \le i \le n$) 都成立。仅当你已经解决了所有版本时，才能进行 Hack。
你有两个由正整数组成的数组 $a$ 和 $b$，它们的长度均为 $n$。你可以进行如下操作任意次（也可以一次都不做）：
- 选择一个整数 $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$ 的最大公约数。
你有两个由正整数组成的数组 $a$ 和 $b$，它们的长度均为 $n$。你可以进行如下操作任意次（也可以一次都不做）：
- 选择一个整数 $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$ 的最大公约数。
输入格式
每个测试包含多个测试用例。第一行包含整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。每个测试用例的描述如下：
每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示数组 $a$ 的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 2 \times 10^5$）。
第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$\mathbf{1 \le b_i \le 10^9}$）。
所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。
每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示数组 $a$ 的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 2 \times 10^5$）。
第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$\mathbf{1 \le b_i \le 10^9}$）。
所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。
输出格式
对于每个测试用例，输出所需的最小总代价。
输入输出样例
输入 #1
6 2 1 1 1 2 2 4 8 41 67 5 1 1 727 1 1 1 1 1000 1 1 2 3 11 1 1 3 2 7 11 1 6 6 3 2 7 11 100 1 2
输出 #1
3 0 2 1 5 1
说明/提示
在第一个测试用例中，我们可以这样操作：$[\mathbf{1}, 1] \xrightarrow{x = 1} [2, \mathbf{1}] \xrightarrow{x = 2} [2, 2]$，总花费为 $1+2 = 3$。现在 $\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) > 1$。不需要进行任何操作。
在第二个测试用例中，$\gcd(a_1, a_2) = 4$，因此 $\gcd(a_1, a_2) > 1$。不需要进行任何操作。