← 返回题目列表

Codeforces · 2170/C

C. 商和余数

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

给定两个整数数组:$$$q_1、q_2、\dots、q_n$$$ 和 $$$r_1、r_2、\dots、r_n$$$,以及一个整数 $$$k$$$。

您可以执行以下操作任意次数(可能为零):

  1. 选择两个整数 $$$x$$$ 和 $$$y$$$ 使得
    • $$$1 \le y \lt 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$$$ 中多次出现 $$$q_i$$$,则只删除其中的一个; $$$r_j$$$ 和数组 $$$r$$$ 相同。

计算可以对给定数组 $$$q$$$ 和 $$$r$$$ 执行的最大操作数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 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 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 您可以对给定数组执行的最大操作数。

示例

输入
复制

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
0
3

注意

在第一个测试用例中,可以执行一个操作:您可以选择 $$$x = 69$$$ 和 $$$y = 42$$$。然后 $$$\left\lfloor \frac{69}{42} \right\rfloor = 1 = q_1$$$ 和 $$$69 \bmod 42 = 27 = r_1$$$。

在第二个测试用例中,无法执行任何操作,因为找不到合适的 $$$x$$$ 和 $$$y$$$。

在第三个测试用例中,可以执行三个操作:

  1. $$$x = 42$$$, $$$y = 17$$$: $$$\left\lfloor \frac{42}{17} \right\rfloor = 2 = q_3$$$ 和 $$$42 \bmod 17 = 8 = r_2$$$;
  2. $$$x = 41$$$,$$$y = 16$$$:$$$\left\lfloor \frac{41}{16} \right\rfloor = 2 = q_4$$$ 和 $$$41 \bmod 16 = 9 = r_1$$$;
  3. $$$x = 20$$$,$$$y = 12$$$:$$$\left\lfloor \frac{20}{12} \right\rfloor = 1 = q_5$$$ 和 $$$20 \bmod 12 = 8 = r_4$$$;
经过这些操作,您将得到数组 $$$q = [5, 4]$$$ 和 $$$r = [9, 100]$$$,并且您无法执行更多操作。