这是问题的困难版本。版本之间的区别在于,在该版本中,$$$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$$$。
输出
对于每个测试用例,输出可以完成的最大操作数。
示例
输入复制
971 2 3 4 5 6 7100 6 12 20 5 2 7367 67 671000000000 1000000000 100000000068 10 10 12 12 141 1 1 1 1 182010 330 550 2 210 385 1001 3232010 1000 1200 30 500 1000 2000 100041 2 4 31 1 1 162 3 4 5 1 610 15 20 25 5 3021 22 10052860 2860 143 9009 90092860 2860 1430 9009 900932 60 6010 60 60
输出复制
730716200
注意
在第一个测试中,由于所有子数组的 gcd 都是 $$$1$$$,因此我们可以将数组更改为 $$$a' = [67, 5, 7, 11, 1, 2, 1]$$$。这里我们执行了 $$$7$$$ 操作,并且由于数组中只有 $$$7$$$ 元素,因此它是可能的最大值。
在第二个测试用例中,我们可以将数组更改为 $$$a' = [938, 2613, 4489]$$$。可以看出,经过这个变换,所有子数组的gcd保持不变。因此这里的答案是$$$3$$$。
在第三个测试用例中,可以看出无法执行任何操作,因此答案为$$$0$$$。