CF1973F Maximum GCD Sum Queries

对于 $k$ 个正整数 $x_1, x_2, \ldots, x_k$，$\gcd(x_1, x_2, \ldots, x_k)$ 表示这些整数的最大公约数——即最大的整数 $z$，使得所有 $x_1, x_2, \ldots, x_k$ 都能被 $z$ 整除。 现在给定三个长度为 $n$ 的数组 $a_1, a_2, \ldots, a_n$，$b_1, b_2, \ldots, b_n$ 和 $c_1, c_2, \ldots, c_n$，其中每个元素都是正整数。 你有一台机器，可以对任意 $i$（$1 \leq i \leq n$）交换 $a_i$ 和 $b_i$，每次交换需要花费 $c_i$ 个金币。 请你在总花费不超过 $d$ 个金币的前提下，通过若干次交换，使得 $\gcd(a_1, a_2, \ldots, a_n) + \gcd(b_1, b_2, \ldots, b_n)$ 的值最大。金币数量会有多种情况，请你对于每个可能的金币数 $d_1, d_2, \ldots, d_q$，分别求出最大值。

第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 5 \times 10^5$，$1 \leq q \leq 5 \times 10^5$）。 第二行包含 $n$ 个整数，表示 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^8$）。 第三行包含 $n$ 个整数，表示 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 10^8$）。 第四行包含 $n$ 个整数，表示 $c_1, c_2, \ldots, c_n$（$1 \leq c_i \leq 10^9$）。 第五行包含 $q$ 个整数，表示 $d_1, d_2, \ldots, d_q$（$0 \leq d_i \leq 10^{15}$）。

输出 $q$ 个整数，第 $i$ 个整数表示在金币数为 $d_i$ 时能获得的最大值。

在第一个样例的第一个询问中，不能进行任何交换，所以答案为 $\gcd(1, 2, 3) + \gcd(4, 5, 6) = 2$。在第二个询问中，可以交换 $a_2$ 和 $b_2$，此时答案为 $\gcd(1, 5, 3) + \gcd(4, 2, 6) = 3$。 在第二个样例的第二个询问中，最优做法是在第 $1$ 和第 $3$ 个位置进行交换，此时答案为 $\gcd(3, 3, 6, 9, 3) + \gcd(8, 4, 4, 8, 4) = 7$，总共需要花费 $40$ 个金币。 由 ChatGPT 4.1 翻译