商余配对

【题目描述】

小灰灰有两个长度均为 $n$ 的数组 $q$ 和 $r$，其中 $q_i$ 为正整数，$r_i$ 为非负整数。另有一个正整数 $k$。

一次操作中，可以从数组 $q$ 中选择一个尚未删除的数 $a$，从数组 $r$ 中选择一个尚未删除的数 $b$。如果存在两个正整数 $x,y$，满足

$$y\le x\le k$$

且 $x$ 除以 $y$ 的商为 $a$、余数为 $b$，那么可以将这两个数同时删除。

每个数最多只能被删除一次。请问最多可以删除多少对数？

本题包含多组测试数据。

---

【输入描述】

第一行输入一个正整数 $T$，表示测试数据组数。

接下来依次输入 $T$ 组测试数据。对于每组测试数据：

第一行输入两个正整数 $n,k$。

第二行输入 $n$ 个正整数 $q_1,q_2,\ldots,q_n$。

第三行输入 $n$ 个非负整数 $r_1,r_2,\ldots,r_n$。

保证：

• $1\le T\le 10$；
• $1\le n\le 2\times 10^5$；
• $2\le k\le 10^{18}$；
• $1\le q_i\le 10^9$；
• $0\le r_i\le 10^9$；
• 单个测试点内所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

---

【输出描述】

对于每组测试数据，输出一行一个整数，表示最多可以删除的数对数量。

---

【样例 1】

【样例 1 输入】

1
3 6
1 2 3
0 1 1

【样例 1 输出】

3

【样例 1 解释】

可以将 $(a,b)=(2,1)$ 配对，此时可取 $y=2,x=5$。

可以将 $(a,b)=(1,1)$ 配对，此时可取 $y=2,x=3$。

可以将 $(a,b)=(3,0)$ 配对，此时可取 $y=1,x=3$。

因此最多可以删除 $3$ 对。

---

【样例 2】

【样例 2 输入】

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

【样例 2 输出】

5

【样例 2 解释】

对于每个 $a_i$，都可以选择 $b=0,y=1,x=a_i$，且满足 $1\le x\le 5$，所以 $5$ 对都能删除。

---

【样例 3】

见选手目录下的 Data/sample3.in 和 Data/sample3.ans。

该样例满足每组测试数据 $n\le 10$。

---

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans。

该样例满足对所有 $i$，均有 $r_i=0$。

---

【样例 5】

见选手目录下的 Data/sample5.in 和 Data/sample5.ans。

该样例满足对所有 $i$，均有 $q_i=1$。

---

【样例 6】

见选手目录下的 Data/sample6.in 和 Data/sample6.ans。

该样例满足每组测试数据 $n\le 120$。

---

【样例 7】

见选手目录下的 Data/sample7.in 和 Data/sample7.ans。

该样例满足单个测试点内所有测试数据的 $n$ 之和不超过 $5000$。

---

【样例 8】

见选手目录下的 Data/sample8.in 和 Data/sample8.ans。

该样例无特殊性质。

---

【数据规模与约定】

测试点编号	分数	特殊性质
1 ~ 2	10	每组测试数据 $n\le 10$
3 ~ 5	15	对所有 $i$，均有 $r_i=0$
6 ~ 8		对所有 $i$，均有 $q_i=1$
9 ~ 11	20	每组测试数据 $n\le 120$
12 ~ 14		单个测试点内所有测试数据的 $n$ 之和不超过 $5000$
15 ~ 18		无

点击下载本题选手目录