← 返回题目列表

Codeforces · 2048/F

F. 凯文和数学课

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

凯文是一名来自永眠镇的学生,目前正在上数学课,老师正在给他做除法练习。

黑板上写着两行正整数,每行包含 $$$ n $$$ 数字。第一行是 $$$ a_1, a_2, \ldots, a_n $$$,第二行是 $$$ b_1, b_2, \ldots, b_n $$$。

对于每个除法练习,Kevin 可以选择任意段 $$$ [l, r] $$$ 并找到 $$$ b_l, b_{l+1}, \ldots, b_r $$$ 中的最小值 $$$ x $$$。然后,他将 $$$ l \leq i \leq r $$$ 的每个 $$$ a_i $$$ 修改为 $$$ a_i $$$ 除以 $$$ x $$$ 的上限。

正式地,他选择两个整数 $$$ 1 \leq l \leq r \leq n $$$,设置 $$$ x = \min_{l \leq i \leq r} b_i $$$,并将 $$$ l \leq i \leq r $$$ 的所有 $$$ a_i $$$ 更改为 $$$ \lceil \frac{a_i}{x} \rceil $$$。

当所有 $$$ a_i $$$ 变成 $$$ 1 $$$ 时,Kevin 可以下课回家。他渴望离开,并想知道实现这一目标所需的最少除法练习次数。

输入

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

每个测试用例的第一行包含一个整数 $$$ n $$$ ($$$ 1 \le n \leq 2 \cdot 10^5 $$$) — 序列 $$$ a $$$ 和 $$$ b $$$ 的长度。

每个测试用例的第二行包含 $$$ n $$$ 整数 $$$ a_1, a_2, \ldots, a_n $$$ ($$$ 1 \le a_i \le 10^{18} $$$) — 棋盘上的第一行整数。

每个测试用例的第三行包含 $$$ n $$$ 整数 $$$ b_1, b_2, \ldots, b_n $$$ ($$$ 2 \le b_i \le 10^{18} $$$) — 棋盘上的第二行整数。

保证所有测试用例的 $$$ n $$$ 之和不超过 $$$ 2 \cdot 10^5 $$$。

输出

对于每个测试用例,输出一个整数——离开课堂所需的最小除法练习数。

示例

输入 #1

3
3
5 4 2
6 3 2
5
3 6 1 3 2
3 5 3 2 2
6
8 3 3 7 5 8
3 2 3 4 2 3

输出 #1

2
3
3

注意

对于第一个测试用例:$$$ [{\color{red}{5,4}},2]\xrightarrow[\min(b_1,b_2)=3]{\text{操作段}[1,2]}[{\color{red}{2,2,2}}]\xrightarrow[\min(b_1,b_2,b_3)=2]{\text{操作段}[1,3]}[1,1,1]$$$。

对于第二个测试用例:$$$ [{\color{red}{3,6,1}},3,2]\xrightarrow[\min(b_1,b_2,b_3)=3]{\text{操作段}[1,3]}[1,{\color{red}{2,1,3}},2]\xrightarrow[\min(b_2,b_3,b_4)=2]{\text{操作段 }[2,4]}[1,1,1,{\color{red}{2,2}}]\xrightarrow[\min(b_4,b_5)=2]{\text{操作段}[4,5]}[1,1,1,1,1]$$$。