CF1946F.Nobody is needed

Oleg 收到了一份长度为 $n$ 的排列 $a$ 作为生日礼物。

Oleg 的朋友 Nechipor 向 Oleg 提出了 $q$ 个问题，每个问题由两个数字 $l$ 和 $r$ 表示，Oleg 需要回答 Nechipor 的每个问题，对于每个问题，Oleg 需要说出满足以下条件的所有下标集合 $(t_1, t_2, \ldots, t_k)$（任意长度 $k \ge 1$）的数量：

• 对于每个 $i$，$1 \le i \le k$，都有 $l \le t_i \le r$。
• 对于每个 $i$，$1 \le i \le k-1$，都有 $t_i < t_{i+1}$。
• 对于每个 $i$，$1 \le i \le k-1$，都有 $a_{t_{i+1}}$ 能被 $a_{t_i}$ 整除。

请帮助 Oleg 回答所有 Nechipor 的问题。

每个测试包含若干组输入数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示输入数据组数。每组输入数据的描述如下：

每组输入数据的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 10^6$），分别表示排列的长度和 Nechipor 的问题数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示排列 $a$。

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示 Nechipor 的一个问题。

保证所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $10^6$。

对于每组输入数据，输出所有 Nechipor 问题的答案。

第一组输入数据中所有符合条件的数组有：（$1$）、（$2$）、（$3$）、（$4$）、（$5$）、（$6$）、（$7$）、（$8$）、（$1, 3$）、（$1, 6$）、（$1, 7$）、（$1, 6, 7$）、（$2, 3$）、（$2, 4$）、（$2, 5$）、（$2, 6$）、（$2, 7$）、（$2, 8$）、（$2, 6, 7$）、（$6, 7$）。

第四组输入数据中所有符合条件的数组有：（$1$）、（$2$）、（$3$）、（$4$）、（$5$）、（$6$）、（$7$）、（$8$）、（$1, 2$）、（$1, 3$）、（$1, 4$）、（$1, 5$）、（$1, 6$）、（$1, 7$）、（$1, 8$）、（$1, 2, 4$）、（$1, 2, 6$）、（$1, 2, 8$）、（$1, 2, 4, 8$）、（$1, 3, 6$）、（$1, 4, 8$）、（$2, 4$）、（$2, 6$）、（$2, 8$）、（$2, 4, 8$）、（$3, 6$）、（$4, 8$）。

由 ChatGPT 4.1 翻译