CFCF2154C2.No Cost Too Great (Hard Version)

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

这是该问题的难度较高版本。不同之处在于本版本中 $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$ 的最大公约数。

输入格式

每个测试包含多个测试用例。第一行包含整数 $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$ 。

输出格式

对于每个测试用例，输出所需的最小总代价。

输入输出样例

输入#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

说明/提示

在第一个测试用例中，我们可以这样操作： $[\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$ 。不需要进行任何操作。

首页