Loading... # ACWing 246 区间最大公约数 题解 ## 题目描述 给定一个长度为$N$的数列$A$，以及$M$条指令，每条指令可能是以下两种之一： 1. `C l r d`，表示把$A[l],A[l+1],…,A[r]$都加上 dd。 2. `Q l r`，表示询问$A[l],A[l+1],…,A[r]$的最大公约数($GCD$)。 对于每个询问，输出一个整数表示答案。 ## 输入 第一行两个整数$N,M$。 第二行$N$个整数$A[i]$。 接下来$M$行表示$M$条指令，每条指令的格式如题目描述所示。 ## 输出 对于每个询问，输出一个整数表示答案。 每个答案占一行。 ## 解题思路 首先考虑这道题目所支持的操作，其支持的操作一共有两种：区间修改和区间求最大公约数，这样的操作可以用线段树来维护。 其中， 对于区间修改的操作， 可以通过维护差分数组转换为单点修改，这样子可以避免维护懒标记。 但这样子操作也会带来问题：数组的每一个元素`w[i]`表示为`a[i] - a[i - 1]`，区间的最大公约数应该如何求得？为了求解这个问题， 需要从辗转相除法开始解释 ### 辗转相除法 辗转相除法描述的是这样子的问题：设$a > b$且$t = gcd(a, b)$， 则应有$t = gcd(a, b) = gcd(b, a - b)$, 下面给出定理的证明， 不妨设$t_1 = gcd(a, b), t_2 = gcd(b, a - b)$, 分别从$t_1 = gcd(t_1, t_2)$、$t_2=gcd(t_1, t_2)$两个方向证明 #### $t_1=gcd(t_1, t_2)$证明 由$t_1 = gcd(a, b)$, 易得$a = k_1t_1, b = k_2t_1$, 则$t_2 = gcd(k_2t_1, (k_1-k_2)t_1)$, 因此可得$t_1=gcd(t_1, t_2)$ #### $t_2=gcd(t_1, t_2)$证明 由$t_2 = gcd(b, b - a)$, 易得$b = k_1t_2, b - a = k_2t_2$, 则$t_1 = gcd((k_1 - k_2)t_2, k_1t_2)$, 因此可得$t_2=gcd(t_1, t_2)$ ### $t = gcd(x_1, x_2, \cdots, x_n) = gcd(x_1, x_2 - x_1, \cdots, x_n - x_{n - 1})$证明 证明方式同上， 因此可以得到， 为了求的$gcd(l, r)$, 我们只需要求得$l$到$r$的差分数组的最大公约数和`a[l]`的最大公约数， 即为总体的最大公约数。 ## AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #define endl '\n' using namespace std; typedef long long LL; typedef struct Node { int l, r; LL sum, gcd; } node; const int N = 5e5 + 10; int n, m; LL a[N]; node tr[4 * N]; LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } void pushup(node& root, node& left, node& right) { root.sum = left.sum + right.sum; root.gcd = gcd(left.gcd, right.gcd); } void pushup(int u) { pushup(tr[u], tr[u << 1], tr[u << 1 | 1]); } void build(int u, int l, int r) { if(l == r) tr[u] = {l, r, a[l] - a[l - 1], a[l] - a[l - 1]}; else { tr[u] = {l, r}; int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(u); } } node query(int u, int l, int r) { if(tr[u].l >= l && tr[u].r <= r) return tr[u]; int mid = tr[u].l + tr[u].r >> 1; if(r <= mid) return query(u << 1, l, r); else if(l > mid) return query(u << 1 | 1, l, r); else { node left = query(u << 1, l, r); node right = query(u << 1 | 1, l, r); node root; pushup(root, left, right); return root; } } void modify(int u, int x, LL y) { if(tr[u].l == x && tr[u].r == x) { LL b = tr[u].sum + y; tr[u] = {x, x, b, b}; } else { int mid = tr[u].l + tr[u].r >> 1; if(x <= mid) modify(u << 1, x, y); else modify(u << 1 | 1, x, y); pushup(u); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 1; i <= n; i ++) cin >> a[i]; build(1, 1, n); char c; while(m --) { cin >> c; if(c == 'C') { int l, r; LL d; cin >> l >> r >> d; modify(1, l, d); if(r < n) modify(1, r + 1, -d); } else { int l, r; cin >> l >> r; node tmp1 = l + 1 <= r ? query(1, l + 1, r) : node({0, 0, 0, 0}); node tmp2 = query(1, 1, l); cout << abs(gcd(tmp2.sum, tmp1.gcd)) << endl; } } return 0; } ``` 最后修改：2025 年 04 月 27 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏