python

7.7 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 246. 区间最大公约数

一、题目描述

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

C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d
Q l r，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。

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

输入格式 第一行两个整数 N,M。

第二行 N 个整数 A[i] 。

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

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

每个答案占一行。

数据范围 N≤500000,M≤100000,1≤A[i]≤10^{18},|d|≤10^{18}, 保证数据在计算过程中不会超过 long long 范围。

输入样例：

输出样例：

1
2
4

二、解题思路

1、更相减损术

根据更相减损术

有：\large gcd(a,b)=gcd(a,b−a)

最大公约数有这样一个性质： \large gcd(a_1,a_2,…,a_n)=gcd(a_1,a_2−a_1,…,a_n−a_{n−1})

证明(为保证题解的主体部分清晰，证明放在最后)

我们想要求的就是：\large (A_l,A_{l+1},A_{l+2}…A_r)这个区间的 最大公约数

根据上面的 更相减损数理论，就是在求下面区间的 最大公约数:

\large (A[l],A[l+1]−A[l],A[l+2]−A[l+1],A[l+3]−A[l+2],…,A[r]−A[r−1])

稍微转化一下，得到：

\large (A[l],b[l+1],b[l+2],b[l+3],…,b[r])

这个东西要一分两半来看：

① A[l]:因为我们维护的是一个差分数组的线段树,所以可以转化为差分的写法：
```
\large A[l]=sum(b[1],b[2],...,b[l])
```
② 后面的那一坨
```
\large (b[l+1],b[l+2],b[l+3],…,b[r])
```
就是区间l+1 \sim r的最大gcd值，这个东西在线段树的节点上以结构体形式保存着呢，可以直接Node right=query(1,l+1,r)查询出来,right.d就是最大公约数
③ 最后两者打一下擂台： 求\large (A_l,A_{l+1},A_{l+2}…A_r)这个区间的最大公约数，就是

res=abs(gcd(left.sum,right.d))

2、差分数组

因为涉及到 区间修改 的问题，上面的分析已经很清楚，需要引入差分数组解决，如果引入了差分数组，那么区间的+修改动作，可以转化两个点的修改动作，即区间修改通过差分数组简化为单点修改。

设原数组为a[i]，对应的差分数组 b[i]：b_i=a_i−a_{i−1}

那么线段树维护这个b数组就可得到 单点修改从而改变整个区间 的效果。

3、负数的最大公约数

注意gcd操作是没有负数的，所以需要进行abs。

三、实现代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 500010;

int n, m;
LL a[N];

struct Node {
    int l, r;
    LL sum; // 区间总和
    LL d;   // 区间内的最大公约数
} tr[N << 2];

// 求最大公约数
LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

// 函数重载
void pushup(Node &u, Node &l, Node &r) {
    u.sum = l.sum + r.sum; // 更新父节点的区间和
    u.d = gcd(l.d, r.d);   // 计算区间的最大公约数
}
void pushup(int u) {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

// 构建
void build(int u, int l, int r) {
    tr[u] = {l, r}; // 构建时，最重要的是确定区间范围
    if (l == r) {
        LL b = a[r] - a[r - 1]; // 更相减损数,所以按原数组差分构建,yxc大佬很良心修改了试题，添加了1e18的数据范围说明
        tr[u] = {l, r, b, b};   // 当是叶子节点时，区间和就是自己，区间最大公约数也是自己
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    // 子节点变更需要更新父节点需要更新父节点的总和、最大公约数
    pushup(u);
}

// 以u为根的子树中，修改位置为x的节点，值为+v
void modify(int u, int x, LL v) {
    if (tr[u].l == tr[u].r) { // 叶子
        tr[u].sum += v;       // 叶子值+d
        tr[u].d = tr[u].sum;  // 叶子，就是一个数，不是区间，最大公约数是自身
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (x <= mid)                 // x在左侧
        modify(u << 1, x, v);     // 让左儿子处理
    else                          // x在右侧
        modify(u << 1 | 1, x, v); // 让右儿子处理
    // u的子节点数据变更，需要从u开始向上更新父节点信息
    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);
    if (l > mid) return query(u << 1 | 1, l, r);

    Node left = query(u << 1, l, mid);
    Node right = query(u << 1 | 1, mid + 1, r);
    // 合并区间结果 
    Node res;
    pushup(res, left, right);
    return res;
}

int main() {
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 因为差分的r+1可能越界，这里在建立线段树时就多创建一个位置就OK!
    build(1, 1, n + 1); // 看来线段树也没有必要可丁可卯，开大1个2个也没啥问题

    int l, r;
    LL d;
    char op;
    while (m--) {
        cin >> op >> l >> r;
        if (op == 'Q') {
            Node left = query(1, 1, l); // 1~l求sum
            // 如果存在后半段
            if (l < r) {
                Node right = query(1, l + 1, r);
                printf("%lld\n", abs(gcd(left.sum, right.d)));
            } else // l==r
                // 如果不存在后半段，那么就只有前半部分的sum和
                printf("%lld\n", abs(left.sum));
        } else {
            cin >> d;
            // 差分
            modify(1, l, d), modify(1, r + 1, -d);
        }
    }
    return 0;
}

四、多项的更相减损数证明

这里简单证明一下，根据性质gcd(a,b)=gcd(b,a)，gcd(a,b)=gcd(a,b−a)，gcd(a,b,c)=gcd(gcd(a,b),c)，有

\large 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)\\

练习

例题：求(326,78)

326=4×78+14(78,14) 78=5×14+8 (14,8) 14=1×8+6 (6,8) 8=1×6+2 (6,2) 6=3×2 (0,2) 所以(326,78)=2。这和我们用更相减损术算出来的结果是一样的。

例题：求(4,18,22,16)

　　取最小的数4,其他的每一个数都与之相减，结果与4组成新的一组数，那么新数组与原数组的最大公因数相等，当出现零以后，排开零对剩下的数进行相同的处理。即：

(4,18,22,16)=(4,14+4,18+4,12+4)=(4,14,18,12) =(4,10,14,8)=(4,6,10,4)=(4,2,6,0)=(0,2,2,4)=(0,2,0,2)=(0,0,2,0)=2 所以(4,18,22,16)的最大公因数为2.

7.7 KiB Raw Permalink Blame History Unescape Escape