Maximums and Minimums

题意翻译

求有多少区间的最大值是最小值的倍数。

题目描述

You are given an array $ a_1, a_2, \ldots, a_n $ of positive integers. Find the number of pairs of indices $ (l, r) $ , where $ 1 \le l \le r \le n $ , that pass the check. The check is performed in the following manner: 1. The minimum and maximum numbers are found among $ a_l, a_{l+1}, \ldots, a_r $ . 2. The check is passed if the maximum number is divisible by the minimum number.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10 $ ) — the number of test cases. Then the test cases follow. Each test case consists of two lines. The first line contains a single integer $ n $ ( $ 1 \le n \le 5 \cdot 10^5 $ ) — the size of the array. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^6 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5 \cdot 10^5 $ .

输出格式

For each test case, print a single integer — the number of pairs of indices that pass the check.

输入输出样例

输入样例 #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

说明

Below $ x \mid y $ denotes that $ y $ is divisible by $ x $ . In the first test case, there is one pair $ (1, 1) $ , the maximum for this pair is $ 1 $ , the minimum is also $ 1 $ , $ 1 \mid 1 $ , so the check is passed, and the answer is $ 1 $ . In the second test case, there are $ 3 $ segments: - $ (1, 1) $ : the maximum is $ 2 $ , the minimum is $ 2 $ , $ 2 \mid 2 $ , so the check is passed. - $ (1, 2) $ : the maximum is $ 4 $ , the minimum is $ 2 $ , $ 2 \mid 4 $ , so the check is passed. - $ (2, 2) $ : the maximum is $ 4 $ , the minimum is $ 4 $ , $ 4 \mid 4 $ , so the check is passed. In the third test case, there are $ 3 $ segments: - $ (1, 1) $ : the maximum is $ 2 $ , the minimum is $ 2 $ , $ 2 \mid 2 $ , so the check is passed. - $ (1, 2) $ : the maximum is $ 3 $ , the minimum is $ 2 $ , $ 3 $ isn't divisible by $ 2 $ , so the check is failed. - $ (2, 2) $ : the maximum is $ 3 $ , the minimum is $ 3 $ , $ 3 \mid 3 $ , so the check is passed.

**最大值和最小值**

**题意翻译**
求有多少区间的最大值是最小值的倍数。

**题目描述**
给定一个正整数数组 $ 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 $。

在第二个测试用例中，有三个区间：

- $ (1, 1) $：最大值是 $ 2 $，最小值是 $ 2 $，$ 2 \mid 2 $，所以检查通过。
- $ (1, 2) $：最大值是 $ 4 $，最小值是 $ 2 $，$ 2 \mid 4 $，所以检查通过。
- $ (2, 2) $：最大值是 $ 4 $，最小值是 $ 4 $，$ 4 \mid 4 $，所以检查通过。

在第三个测试用例中，有三个区间：

- $ (1, 1) $：最大值是 $ 2 $，最小值是 $ 2 $，$ 2 \mid 2 $，所以检查通过。
- $ (1, 2) $：最大值是 $ 3 $，最小值是 $ 2 $，$ 3 $ 不能被 $ 2 $ 整除，所以检查失败。
- $ (2, 2) $：最大值是 $ 3 $，最小值是 $ 3 $，$ 3 \mid 3 $，所以检查通过。**最大值和最小值** **题意翻译** 求有多少区间的最大值是最小值的倍数。 **题目描述** 给定一个正整数数组 $ 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 $。 在第二个测试用例中，有三个区间： - $ (1, 1) $：最大值是 $ 2 $，最小值是 $ 2 $，$ 2 \mid 2 $，所以检查通过。 - $ (1, 2) $：最大值是 $ 4 $，最小值是 $ 2 $，$ 2 \mid 4 $，所以检查通过。 - $ (2, 2) $：最大值是 $ 4 $，最小值是 $ 4 $，$ 4 \mid 4 $，所以检查通过。 在第三个测试用例中，有三个区间： - $ (1, 1) $：最大值是 $ 2 $，最小值是 $ 2 $，$ 2 \mid 2 $，所以检查通过。 - $ (1, 2) $：最大值是 $ 3 $，最小值是 $ 2 $，$ 3 $ 不能被 $ 2 $ 整除，所以检查失败。 - $ (2, 2) $：最大值是 $ 3 $，最小值是 $ 3 $，$ 3 \mid 3 $，所以检查通过。