Array Equalizer

题意翻译

## 题面描述 Jeevan 有两个长度为 $n$ 的数组：$a$ 和 $b$。他有以下两种操作： + 选择一个 $k$（$1 \le k \le n$），对所有满足 $1 \leq i \leq n$ 并且 $1 \le i \times k \le n$ 的 $i$，令 $a_{ik}=a_{ik} + 1$。 + 选择一个 $k$（$1 \le k \le n$），对所有满足 $1 \leq i \leq n$ 并且 $1 \le i \times k \le n$ 的 $i$，令 $a_{ik}=a_{ik} - 1$。 不幸的是，他忘记了 $b_1$，因此他会向你提问 $q$ 次，每次给出一个 $x$，表示： - 如果 $b_1 = x$，那么把 $a$ 变为 $b$ 至少需要几次操作？ ## 输入格式 第一行一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示 $a$ 和 $b$ 的长度。 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）。 第三行 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le 10^6$）。保证 $b_1 = -1$，表示 $b_1$ 是未知的。 第四行一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示询问次数。 接下来 $q$ 行，每行一个整数 $x$（$1 \le x \le 10^6$）。 ## 输出格式 输出 $q$ 行 $q$ 个整数，表示每个询问的答案。

题目描述

Jeevan has two arrays $ a $ and $ b $ of size $ n $ . He is fond of performing weird operations on arrays. This time, he comes up with two types of operations: - Choose any $ i $ ( $ 1 \le i \le n $ ) and increment $ a_j $ by $ 1 $ for every $ j $ which is a multiple of $ i $ and $ 1 \le j \le n $ . - Choose any $ i $ ( $ 1 \le i \le n $ ) and decrement $ a_j $ by $ 1 $ for every $ j $ which is a multiple of $ i $ and $ 1 \le j \le n $ . He wants to convert array $ a $ into an array $ b $ using the minimum total number of operations. However, Jeevan seems to have forgotten the value of $ b_1 $ . So he makes some guesses. He will ask you $ q $ questions corresponding to his $ q $ guesses, the $ i $ -th of which is of the form: - If $ b_1 = x_i $ , what is the minimum number of operations required to convert $ a $ to $ b $ ? Help him by answering each question.

输入输出格式

输入格式

The first line contains a single integer $ n $ $ (1 \le n \le 2 \cdot 10^{5}) $ — the size of arrays $ a $ and $ b $ . The second line contains $ n $ integers $ a_1, a_2, ..., a_n $ $ (1 \le a_i \le 10^6) $ . The third line contains $ n $ integers $ b_1, b_2, ..., b_n $ $ (1 \le b_i \le 10^6 $ for $ i \neq 1 $ ; $ b_1 = -1 $ , representing that the value of $ b_1 $ is unknown $ ) $ . The fourth line contains a single integer $ q $ $ (1 \le q \le 2 \cdot 10^{5}) $ — the number of questions. Each of the following $ q $ lines contains a single integer $ x_i $ $ (1 \le x_i \le 10^6) $ — representing the $ i $ -th question.

输出格式

Output $ q $ integers — the answers to each of his $ q $ questions.

输入输出样例

输入样例 #1

2
3 7
-1 5
3
1
4
3

输出样例 #1

2
4
2

输入样例 #2

6
2 5 4 1 3 6
-1 4 6 2 3 5
3
1
8
4

输出样例 #2

10
29
9

说明

Consider the first test case. - $ b_1 = 1 $ : We need to convert $ [3, 7] \rightarrow [1, 5] $ . We can perform the following operations: $ [3, 7] $ $ \xrightarrow[\text{decrease}]{\text{i = 1}} $ $ [2, 6] $ $ \xrightarrow[\text{decrease}]{\text{i = 1}} $ $ [1, 5] $ Hence the answer is $ 2 $ . - $ b_1 = 4 $ : We need to convert $ [3, 7] \rightarrow [4, 5] $ . We can perform the following operations: $ [3, 7] $ $ \xrightarrow[\text{decrease}]{\text{i = 2}} $ $ [3, 6] $ $ \xrightarrow[\text{decrease}]{\text{i = 2}} $ $ [3, 5] $ $ \xrightarrow[\text{increase}]{\text{i = 1}} $ $ [4, 6] $ $ \xrightarrow[\text{decrease}]{\text{i = 2}} $ $ [4, 5] $ Hence the answer is $ 4 $ . - $ b_1 = 3 $ : We need to convert $ [3, 7] \rightarrow [3, 5] $ . We can perform the following operations: $ [3, 7] $ $ \xrightarrow[\text{decrease}]{\text{i = 2}} $ $ [3, 6] $ $ \xrightarrow[\text{decrease}]{\text{i = 2}} $ $ [3, 5] $ Hence the answer is $ 2 $ .