← 返回题目列表

Codeforces · 1798/C

C. 糖果店

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

商店出售$$$n$$$种糖果,编号从$$$1$$$到$$$n$$$。一颗 $$$i$$$ 类型的糖果需要花费 $$$b_i$$$ 硬币。商店中总共有 $$$a_i$$$ 类型的糖果 $$$i$$$。

您需要将所有可用的糖果打包,每个包只能包含一种类型的糖果。形式上,对于每种类型的糖果 $$$i$$$,您需要选择整数 $$$d_i$$$,表示一包中 $$$i$$$ 类型糖果的数量,以便 $$$a_i$$$ 除以 $$$d_i$$$ 没有余数。

那么一包 $$$i$$$ 类型的糖果的成本将等于 $$$b_i \cdot d_i$$$。我们用 $$$c_i$$$ 来表示这个成本,即 $$$c_i = b_i \cdot d_i$$$。

包装后,包装将被放置在货架上。考虑放置在货架上的包装的成本,按顺序 $$$c_1、c_2、\ldots、c_n$$$。价格标签将用于描述包装的成本。如果 $$$c_l = c_{l+1} = \ldots = c_r$$$,则一个价格标签可以描述从 $$$l$$$ 到 $$$r$$$ 的所有包的成本。从 $$$1$$$ 到 $$$n$$$ 的每一包必须至少用一个价格标签来描述。例如,如果 $$$c_1, \ldots, c_n = [4, 4, 2, 4, 4]$$$,要描述所有包装,$$$3$$$ 价格标签就足够了,第一个价格标签描述包装 $$$1, 2$$$,第二个:$$$3$$$,第三个:$$$4, 5$$$。

给定整数 $$$a_1, b_1, a_2, b_2, \ldots, a_n, b_n$$$。您的任务是选择整数 $$$d_i$$$,使得所有 $$$i$$$ 的 $$$a_i$$$ 都能被 $$$d_i$$$ 整除,并且描述 $$$c_1, c_2, \ldots, c_n$$$ 的值所需的价格标签数量是尽可能的最小值。

为了更好地理解该语句,请看第一个测试的第一个测试用例的图示:

让我们重复一下问题中使用的符号的含义:

$$$a_i$$$ — 商店中可用的 $$$i$$$ 类型糖果的数量。

$$$b_i$$$ — 一颗 $$$i$$$ 类型糖果的成本。

$$$d_i$$$ — 一包中 $$$i$$$ 类型糖果的数量。

$$$c_i$$$ — 一包 $$$i$$$ 类型糖果的成本由公式 $$$c_i = b_i \cdot d_i$$$ 表示。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100\,000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 200\,000$$$) — 糖果类型的数量。

每个测试用例接下来的 $$$n$$$ 行都包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i \le 10^9$$$, $$$1 \le b_i \le 10\,000$$$) - 糖果的数量和一颗糖果类型的成本分别是$$$i$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。

输出

对于每个测试用例,输出描述商店中所有包糖果的成本所需的最少价格标签数量。

示例

输入 #1

5
4
20 3
6 2
14 5
20 7
3
444 5
2002 10
2020 2
5
7 7
6 5
15 2
10 3
7 7
5
10 1
11 5
5 1
2 2
8 2
6
7 12
12 3
5 3
9 12
9 3
1000000000 10000

输出 #1

2
1
3
2
5

注意

在第一个测试用例中,您可以选择 $$$d_1 = 4$$$、$$$d_2 = 6$$$、$$$d_3 = 7$$$、$$$d_4 = 5$$$。那么包的成本将等于 $$$[12, 12, 35, 35]$$$。 $$$2$$$ 价格标签足以描述它们,第一个价格标签为$$$c_1、c_2$$$,第二个价格标签为$$$c_3、c_4$$$。可以证明,只要 $$$d_i$$$ 的任何正确选择,至少需要 $$$2$$$ 的价格标签来描述所有包装。另请注意,该示例是通过声明中的图片进行说明的。

在第二个测试用例中,$$$d_1 = 4$$$、$$$d_2 = 2$$$、$$$d_3 = 10$$$,所有包的成本将等于 $$$20$$$。因此,$$$1$$$ 价格标签足以描述所有包。请注意,对于所有 $$$i$$$,$$$a_i$$$ 可以被 $$$d_i$$$ 整除,这是必要条件。

在第三个测试用例中,不难理解,一个价格标签可以用来描述第 $$$2$$$nd、$$$3$$$rd 和 $$$4$$$th 包。另外还有包装 $$$1$$$ 和包装 $$$5$$$ 的价格标签。总计:$$$3$$$ 价格标签。