← 返回题目列表

Codeforces · 2210/C1

C1. 一个简单的 GCD 问题(简单版)

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

这是问题的简单版本。版本之间的差异在于,在此版本中,$$$1 \leq n \leq 2 \cdot 10^{5}$$$ 和 $$$b_i = a_i$$$ 对于 $$$1 \leq i \leq n$$$。请注意,一个版本的解决方案不一定能解决另一版本的问题。只有解决了该问题的所有版本,您才能破解。

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

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

  • 选择任意整数 $$$m$$$ ($$$\mathbf{m \neq a_i}$$$) 使得 $$$1 \leq m \le 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 2\cdot 10^5$$$) — $$$a$$$ 的长度。

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

每个测试用例的下一行包含 $$$n$$$ 空格分隔的整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$\color{red}{b_i = a_i}$$$)。

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

输出

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

示例

输入
复制

4
7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
3
67 67 67
67 67 67
6
8 10 10 12 12 14
8 10 10 12 12 14
8
2 4 8 16 32 64 128 256
2 4 8 16 32 64 128 256

输出
复制

6
0
2
1

注意

对于第一个测试用例,所有子数组的 GCD 为 $$$1$$$。因此,我们可以执行 $$$6$$$ 操作并将数组更改为 $$$a' = [1, 1, 1, 1, 1, 1, 1]$$$。可以看出,在这种情况下可以执行的最大操作数是$$$6$$$。

对于第二个测试用例,请注意所有值都相等,并且减少任何值都会导致子数组的 GCD 减少。因此,可以执行$$$0$$$操作。

对于第三个测试用例,可以证明最多可以执行$$$2$$$操作。