题目描述

最近，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$ 的查询，输出任务中有趣的连续子数组的数量。

5 1
8 4 3 9 1
2 2 5

4

5 3
2 3 6 4 1
2 1 4
1 3 1
2 3 5

6
1

4 3
2 2 2 2
2 1 4
1 2 3
2 1 4

10
5

提示

第一个测试用例的说明：

从第 $2$ 个位置到第 $5$ 个位置的区间由数字 $(4, 3, 9, 1)$ 组成。在其中，有以下有趣的连续子数组（用方括号表示）：$[4] 3 9 1, 4 [3] 9 1, 4 3 [9] 1, 4 [3 9] 1$。

题面翻译由 ChatGPT-4o 提供。