← 返回题目列表

Codeforces · 1133/D

D. 零数量最大化

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

给定两个数组 $$$a$$$ 和 $$$b$$$,每个数组包含 $$$n$$$ 整数。

您想要创建一个新数组 $$$c$$$,如下所示:选择一些实数(即不一定是整数)数字 $$$d$$$,然后对于 [1, n]$$$ 中的每个 $$$i \in [1, n]$$$ 让 $$$c_i := d \cdot a_i + b_i$$$。

您的目标是最大化数组 $$$c$$$ 中零的数量。如果您最优地选择$$$d$$$,最大可能的答案是多少?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 两个数组中的元素数量。

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)。

第三行包含 $$$n$$$ 整数 $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$)。

输出

打印一个整数 - 如果您选择 $$$d$$$ 为最佳,则数组 $$$c$$$ 中零的最大数量。

示例

输入 #1

5
1 2 3 4 5
2 4 7 11 3

输出 #1

2

输入 #2

3
13 37 39
1 2 3

输出 #2

2

输入 #3

4
0 0 0 0
1 2 3 4

输出 #3

0

输入#4

3
1 2 -1
-6 -12 6

输出#4

3

注意

在第一个示例中,我们可以选择 $$$d = -2$$$。

在第二个示例中,我们可以选择 $$$d = -\frac{1}{13}$$$。

在第三个例子中,无论我们选择哪个$$$d$$$,我们都无法在数组$$$c$$$中获得任何零。

在第四个例子中,我们可以选择$$$d = 6$$$。