#157. 区间最大公约数

区间最大公约数

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 N\red N 的数列 A\red A,以及 M\red M 条指令,每条指令可能是以下两种之一:

1\red 1、“C l r d”,表示把 A[l]\red{A[l]} , A[l+1]\red{A[l+1]} , ......\red{......} , A[r]\red{A[r]} 都加上 d\red d

2\red 2、“Q l r”,表示询问 A[l]\red{A[l]} , A[l+1]\red{A[l+1]} , ......\red{......} , A[r]\red{A[r]} 的最大公约数(GCD)。

对于每个询问,输出一个整数表示答案。

输入格式

第一行两个整数 N\red N , M\red M

第二行 N\red N 个整数 A[i]\red{A[i]}

接下来 M\red M 行表示 M\red M 条指令,每条指令的格式如题目描述所示。

输出格式

对于每个询问,输出一个整数表示答案。

每个答案占一行。

样例

输入样例

5 5
1 3 5 7 9
Q 1 5
C 1 5 1
Q 1 5
C 3 3 6
Q 2 4

输出样例

1
2
4

提示

N500000\red{N\le 500000},

M100000\red{M\le 100000}

数据结构3

未参加
状态
已结束
规则
IOI
题目
19
开始于
2023-1-9 12:00
结束于
2023-1-17 20:00
持续时间
200 小时
主持人
参赛人数
12