← 返回题目列表

Codeforces · 1730/E

E. 最大值和最小值

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

给定一个正整数数组 $$$a_1, a_2, \ldots, a_n$$$。

查找通过检查的索引对 $$$(l, r)$$$ 的数量,其中 $$$1 \le l \le r \le n$$$。检查按以下方式进行:

1. 在 $$$a_l, a_{l+1}, \ldots, a_r$$$ 中找到最小和最大数字。
2. 如果最大数能被最小数整除,则检查通过。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10$$$) — 测试用例的数量。然后是测试用例。

每个测试用例由两行组成。

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 数组的大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$)。

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

输出

对于每个测试用例,打印一个整数 - 通过检查的索引对的数量。

示例

输入 #1

6
1
1
2
2 4
2
2 3
4
2 4 7 14
7
16 5 18 7 7 12 14
6
16 14 2 6 16 2

输出 #1

1
3
2
7
10
19

注意

$$$x \mid y$$$ 下方表示 $$$y$$$ 可以被 $$$x$$$ 整除。

第一个测试用例中有一对$$$(1, 1)$$$,该对的最大值是$$$1$$$,最小值也是$$$1$$$,$$$1 \mid 1$$$,所以检查通过,答案是$$$1$$$。

在第二个测试用例中,有 $$$3$$$ 段:

- $$$(1, 1)$$$:最大值为$$$2$$$,最小值为$$$2$$$,$$$2 \mid 2$$$,因此检查通过。
- $$$(1, 2)$$$:最大为$$$4$$$,最小为$$$2$$$,$$$2 \mid 4$$$,因此检查通过。
- $$$(2, 2)$$$:最大值为$$$4$$$,最小值为$$$4$$$,$$$4 \mid 4$$$,因此检查通过。

在第三个测试用例中,有 $$$3$$$ 段:

- $$$(1, 1)$$$:最大值为$$$2$$$,最小值为$$$2$$$,$$$2 \mid 2$$$,因此检查通过。
- $$$(1, 2)$$$:最大值为$$$3$$$,最小值为$$$2$$$,$$$3$$$不能被$$$2$$$整除,因此检查失败。
- $$$(2, 2)$$$:最大值为$$$3$$$,最小值为$$$3$$$,$$$3 \mid 3$$$,因此检查通过。