区间最大公约数
给定一个长度为 $N$ 的数列 $A$，以及 $M$ 条指令，每条指令可能是以下两种之一：
- C l r d ，表示把 $A[l],A[l+1], \ldots ,A[r]$ 都加上 $d$。
- Q l r ，表示询问 $A[l],A[l+1], \ldots ,A[r]$ 的最大公约数(GCD)。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数 $N,M$。
第二行 $N$ 个整数 $A[i]$。
接下来 $M$ 行表示 $M$ 条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
$N \leq 500000,M \leq 100000$,
$1 \leq A[i] \leq {10}^{18}$,
$|d| \leq {10}^{18}$
输入样例：
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
解题思路
如果没有修改操作只有查询操作，那么直接维护区间的最大公约数就可以了。如果只有单点修改，一样只需要维护区间的最大公约数就可以了。如果是区间修改那么只维护区间最大公约数就不可以了，因为如果给某个区间都加上$x$，那么可以发现$\gcd{(a, b, c)}$与$\gcd{(a+x, b+x, c+x)}$没有什么关系，只根据之前的最大公约数是求不出来加上某个数后的最大公约数的。
最大公约数有这样一个性质：$$\gcd{(a_1, a_2, \ldots, a_n)} = \gcd{(a_1, a_2 - a_1, \ldots, a_n - a_{n-1})}$$
这里简单证明一下，根据性质$\gcd{(a, b)} = \gcd{(b, a)}$，$\gcd{(a, b)} = \gcd{(a, b - a)}$，$\gcd{(a, b, c)} = \gcd{(\gcd{(a, b)}, c)}$，有$$\begin{align*} \gcd{(a, b, c, d)} &= \gcd{(a, b - a, c, d)} \\ &= \gcd{(a, b - a, c - b + a, d)} \\ &= \gcd{(a, b - a, c - b, d)} \\ &= \gcd{(a, b - a, c - b, d - c + b)} \\ &= \gcd{(a, b - a, c - b, d - c + a)} \\ &= \gcd{(a, b - a, c - b, d - c)} \end{align*}$$
可以归纳证明多个变量的情况。
因此可以用线段树来维护一个差分序列，这样区间修改就可以变成单点修改了，在维护区间最大公约数的同时再维护一个区间和。当查询区间$[l, r]$，就是求$\gcd{(a_{l}, a_{l+1} - a_{l}, \ldots, a_{r} - a_{r - 1})}$，$a_{l}$可以用维护的区间和得到，$\gcd{(a_{l+1} - a_{l}, \ldots, a_{r} - a_{r - 1})}$可以用维护的区间最大公约数得到。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 typedef long long LL;
5
6 const int N = 5e5 + 10;
7
8 LL a[N];
9 struct Node {
10 int l, r;
11 LL s, d;
12 }tr[N * 4];
13
14 LL gcd(LL a, LL b) {
15 return b ? gcd(b, a % b) : a;
16 }
17
18 void build(int u, int l, int r) {
19 if (l == r) {
20 tr[u] = {l, r, a[l] - a[l - 1], a[l] - a[l - 1]}; // 维护的是差分序列
21 }
22 else {
23 int mid = l + r >> 1;
24 build(u << 1, l, mid);
25 build(u << 1 | 1, mid + 1, r);
26 tr[u] = {l, r, tr[u << 1].s + tr[u << 1 | 1].s, gcd(tr[u << 1].d, tr[u << 1 | 1].d)};
27 }
28 }
29
30 void modify(int u, int x, LL c) {
31 if (tr[u].l == x && tr[u].r == x) {
32 tr[u].s += c, tr[u].d += c;
33 }
34 else {
35 int mid = tr[u].l + tr[u].r >> 1;
36 if (x <= mid) modify(u << 1, x, c);
37 else modify(u << 1 | 1, x, c);
38 tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
39 tr[u].d = gcd(tr[u << 1].d, tr[u << 1 | 1].d);
40 }
41 }
42
43 Node query(int u, int l, int r) {
44 if (tr[u].l >= l && tr[u].r <= r) return tr[u];
45 int mid = tr[u].l + tr[u].r >> 1;
46 if (r <= mid) {
47 return query(u << 1, l, r);
48 }
49 else if (l >= mid + 1) {
50 return query(u << 1 | 1, l, r);
51 }
52 else {
53 Node t1 = query(u << 1, l, r), t2 = query(u << 1 | 1, l, r);
54 return {l, r, t1.s + t2.s, gcd(t1.d, t2.d)};
55 }
56 }
57
58 int main() {
59 int n, m;
60 scanf("%d %d", &n, &m);
61 for (int i = 1; i <= n; i++) {
62 scanf("%lld", a + i);
63 }
64 build(1, 1, n + 1);
65 while (m--) {
66 char op[5];
67 int l, r;
68 scanf("%s %d %d", op, &l, &r);
69 if (op[0] == 'C') {
70 LL c;
71 scanf("%lld", &c);
72 modify(1, l, c), modify(1, r + 1, -c);
73 }
74 else {
75 LL d = abs(query(1, 1, l).s); // a[l]通过差分序列的前缀和求得
76 if (l + 1 <= r) printf("%lld\n", abs(gcd(d, query(1, l + 1, r).d))); // 当l+1 <= r才存在剩余部分的最大公约数
77 else printf("%lld\n", d);
78 }
79 }
80
81 return 0;
82 }
参考资料
AcWing 246. 区间最大公约数（算法提高课）：https://www.acwing.com/video/650/
标签：gcd,int,LL,最大公约数,区间,ldots From： https://www.cnblogs.com/onlyblues/p/16892364.html