CF1973F.Maximum GCD Sum Queries

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

对于 $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$ 时能获得的最大值。

输入输出样例

输入#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$ 个金币。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页