← 返回题目列表

Codeforces · 1973/F

F. 最大 GCD 和查询

中文机器翻译题面 查看原题

对于 $$$k$$$ 正整数 $$$x_1, x_2, \ldots, x_k$$$,值 $$$\gcd(x_1, x_2, \ldots, x_k)$$$ 是整数的最大公约数 $$$x_1, x_2, \ldots, x_k$$$ — 最大整数$$$z$$$ 使得所有整数 $$$x_1, x_2, \ldots, x_k$$$ 都能被 $$$z$$$ 整除。

给定三个数组 $$$a_1, a_2, \ldots, a_n$$$, $$$b_1, b_2, \ldots, b_n$$$ 和 $$$c_1, c_2, \ldots, c_n$$$,长度为 $$$n$$$,包含正整数。

您还有一台机器,允许您将 $$$a_i$$$ 和 $$$b_i$$$ 交换为任何 $$$i$$$ ($$$1 \le i \le n$$$)。每次交换都会花费您 $$$c_i$$$ 硬币。

找出 $$$$$$\gcd(a_1, a_2, \ldots, a_n) + \gcd(b_1, b_2, \ldots, b_n)$$$$$$ 的最大可能值,您可以通过总共支付最多 $$$d$$$ 硬币来交换某些元素。您拥有的硬币数量变化很大,因此请为每个 $$$q$$$ 可能值 $$$d_1, d_2, \ldots, d_q$$$ 找到此问题的答案。

输入

第一行有两个整数 - 数字 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$, $$$1 \leq q \leq 5 \cdot 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$$$ 整数 — 每个 $$$q$$$ 可能值 $$$d$$$ 可以获得的最大值。

示例

输入 #1

3 4
1 2 3
4 5 6
1 1 1
0 1 2 3

输出 #1

2 3 3 3

输入 #2

5 5
3 4 6 8 4
8 3 4 9 3
10 20 30 40 50
5 55 13 1000 113

输出 #2

2 7 3 7 7

输入 #3

1 1
3
4
5
0

输出 #3

7

注意

在第一个示例的第一个查询中,我们根本不允许进行任何交换,因此答案是 $$$\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$$$ 币。