← 返回题目列表

Codeforces · 2210/C2

C2. 一个简单的 GCD 问题(困难版)

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

这是问题的困难版本。版本之间的区别在于,在该版本中,$$$1 \leq i \leq n$$$ 为 $$$1 \leq n \leq 5 \cdot 10^{4}$$$、$$$1 \leq b_i \leq 10^{9}$$$,时间限制为 $$$6$$$ 秒。请注意,一个版本的解决方案不一定能解决另一版本的问题。只有解决了该问题的所有版本,您才能破解。

给定两个数组 $$$a$$$ 和 $$$b$$$,长度为 $$$n$$$。

对于 各索引 $$$i$$$ ($$$1 \le i \le n$$$) 的数组$$$a$$$,可以执行以下操作 最多一次:

  • 选择任意整数 $$$m$$$ ($$$\mathbf{m \neq a_i}$$$) 使得 $$$1 \leq m \leq b_i$$$,并设置 $$$a_i := m$$$。

令执行完所有操作后的数组为$$$a'$$$。您只能以满足以下条件的方式执行操作:

  • 对于所有 $$$1\leq l \lt r\leq n$$$, $$$\operatorname{gcd}(a_l,a_{l+1},\ldots,{a_r})=\operatorname{gcd}(a'_l,a'_{l+1},\ldots,a'_r)$$$

这里,$$$\gcd(x, y)$$$ 表示整数$$$x$$$ 和$$$y$$$ 的最大公约数(GCD)。

您必须确定 最大 在确保条件仍然满足的情况下可以执行的操作数。

输入

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

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

每个测试用例的以下行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。

每个测试用例的下一行包含 $$$n$$$ 空格分隔的整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$).

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

输出

对于每个测试用例,输出可以完成的最大操作数。

示例

输入
复制

9
7
1 2 3 4 5 6 7
100 6 12 20 5 2 7
3
67 67 67
1000000000 1000000000 1000000000
6
8 10 10 12 12 14
1 1 1 1 1 1
8
2010 330 550 2 210 385 1001 323
2010 1000 1200 30 500 1000 2000 1000
4
1 2 4 3
1 1 1 1
6
2 3 4 5 1 6
10 15 20 25 5 30
2
1 2
2 100
5
2860 2860 143 9009 9009
2860 2860 1430 9009 9009
3
2 60 60
10 60 60

输出
复制

7
3
0
7
1
6
2
0
0

注意

在第一个测试中,由于所有子数组的 gcd 都是 $$$1$$$,因此我们可以将数组更改为 $$$a' = [67, 5, 7, 11, 1, 2, 1]$$$。这里我们执行了 $$$7$$$ 操作,并且由于数组中只有 $$$7$$$ 元素,因此它是可能的最大值。

在第二个测试用例中,我们可以将数组更改为 $$$a' = [938, 2613, 4489]$$$。可以看出,经过这个变换,所有子数组的gcd保持不变。因此这里的答案是$$$3$$$。

在第三个测试用例中,可以看出无法执行任何操作,因此答案为$$$0$$$。