A16730 | $Quotient and Remainder$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定两个整数数组 $q_1, q_2, \dots, q_n$ 和 $r_1, r_2, \dots, r_n$，以及一个整数 $k$。 你可以进行如下操作任意次数（可以为零）： 1. 选择两个整数 $x$ 和 $y$，满足： - $1 \le y < x \le k$； - 存在下标 $i$，使得 $q_i = \left\lfloor \frac{x}{y} \right\rfloor$（向下取整）； - 存在下标 $j$，使得 $r_j = x \bmod y$。 2. 从数组 $q$ 中移除 $q_i$，从数组 $r$ 中移除 $r_j$。如果 $q$ 或 $r$ 中存在多个相同的元素，仅移除一个即可。 计算在给定的数组 $q$ 和 $r$ 上你最多可以进行多少次这样的操作。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \times 10^5$，$2 \le k \le 10^{18}$），即数组 $q$ 和 $r$ 的长度，以及 $x$ 和 $y$ 的上界。 第二行包含 $n$ 个整数 $q_1, q_2, \dots, q_n$（$1 \le q_i \le 10^9$），即数组 $q$。 第三行包含 $n$ 个整数 $r_1, r_2, \dots, r_n$（$1 \le r_i \le 10^9$），即数组 $r$。 输入的额外约束：所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示最多可以进行多少次操作。

输入 #1

3
1 100
1
27
3 10
5 6 5
7 1 7
5 42
5 4 2 2 1
9 8 9 8 100

输出 #1

1
0
3

C++ 编辑器

输入

输出