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

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

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