P4435 [COCI 2017/2018 #2] ​​Garaža

最近，Slavko 一直在研究自然数序列。他认为一个序列是有趣的，如果序列中所有元素的最大公约数大于 $1$。 昨天，他在车库里找到了一个由 $N$ 个自然数组成的序列。由于他感到非常无聊，他决定通过提出简单的查询来打发时间。每个查询可以是以下两种类型之一： 1. 将序列中位置 $X$ 的值更改为 $V$。 2. 确定序列中区间 $[L, R]$ 内包含的有趣连续子数组的数量。

输入的第一行包含数字 $N$ 和 $Q (1 \le N, Q \le 10^5)$，分别表示序列中的元素数量和查询的数量。 接下来的行包含 $N$ 个自然数 $A_i (1 \le A_i \le 10^9)$，表示初始序列中的数字。 接下来的 $Q$ 行中的每一行包含一个查询，格式如下： - 行中的第一个数字可以是 $1$ 或 $2$，表示查询的类型。 - 如果查询是类型 $1$，后面跟着两个数字 $X (1 \le X \le N)$ 和 $V (1 \le V \le 10^9)$。 - 如果查询是类型 $2$，后面跟着两个数字 $L$ 和 $R (1 \le L \le R \le N)$，表示左边界和右边界。

对于每个类型 $2$ 的查询，输出任务中有趣的连续子数组的数量。

**第一个测试用例的说明：** 从第 $2$ 个位置到第 $5$ 个位置的区间由数字 $(4, 3, 9, 1)$ 组成。在其中，有以下有趣的连续子数组（用方括号表示）：$[4] 3 9 1, 4 [3] 9 1, 4 3 [9] 1, 4 [3 9] 1$。 题面翻译由 ChatGPT-4o 提供。