首页 > 其他分享 >NC15557 连续区间的最大公约数

NC15557 连续区间的最大公约数

时间:2023-05-03 23:11:23浏览次数:56  
标签:gcd int NC15557 最大公约数 ans 区间 first GCD

题目链接

题目

题目描述

给一个数列共n(n<=100,000)个数,a1,a2,...,an.(0<=ai<=1000,000,000).有q(q<=100,000)个询问。每个询问为l,r(1<=l<=r<=n).求gcd(al,al+1,...,ar).
再求区间[l,r]的子区间中(l<=l'<=r'<=r)满足gcd(al,al+1,...,ar) = gcd(al',al'+1,...ar')的子区间个数.

输入描述

第一行一个数T表示数据组数
第二行一个数n
接下来一行n个数,a1,a2,...,an
接下一行一个数q
接下来一行2个数l和r。

输出描述

首先输出一行“Case #:t”,t代表当前是第几组数据。
接下来q行,每行输出2个数,第一个是gcd(al,al+1,...,ar),
第二个是区间[l,r]的子区间中(l<=l'<=r'<=r)满足gcd(al,al+1,...,ar) = gcd(al',al'+1,...ar')的子区间个数。

示例1

输入

2
5
1 2 4 6 7
4
1 5
2 4
3 4
4 4
5
1 2 4 2 1
6
1 1
1 3
2 2
2 3
2 4
3 3

输出

Case #1:
1 8
2 4
2 1
6 1
Case #2:
1 1
1 3
2 1
2 2
2 5
4 1

题解

知识点:线段树,最大公约数,双指针,枚举。

区间信息需要维护区间 \(\gcd\) \(GCD\)、区间答案 \(ans\) 。但是,仅通过孩子区间 \(ans\) 是无法获得区间 \(ans\) 的,因为符合条件的子区间可能还包括区间中凭空产生的跨越两个孩子区间的子区间,即和孩子区间 \(ans\) 中的子区间没有任何关系的子区间。因此,我们需要维护额外的信息。

首先,考虑如何从区间中间开始,枚举出跨越两个孩子区间的符合条件的子区间。最朴素的想法是 \(O(n^2)\) 枚举每个端点,但是显然是不行的,我们考虑如何优化。

注意到,子区间 \(\gcd\) 随着区间变大一定是不增的,而区间 \(\gcd\) 一定是最小的,因此我们可以采用尺取法。初始时,左右端点 \(l,r\) 分别在左右子区间的左端点,随后枚举 \(l\) 扩展 \(r\) ,每次 \(r\) 扩展使得 \([l,r]\) 的 \(\gcd\) 变小直到等于区间 \(gcd\) ,那么 \(r\) 到区间右端点的所有点都是当前 \(l\) 的合法右端点(因此还需要维护区间长度 \(len\) ),最后 \(l\) 向右挪一个点,直到 \(l,r\) 到左右子区间的右端点结束。但是,这样的复杂度是 \(O(n)\) 的,显然还是不够的,我们需要继续优化。

我们发现,尺取的过程中 \(\gcd\) 变化频率通常是很小的。实际上, \(l,r\) 的移动有很长一段距离, \([l,r]\) 的 \(\gcd\) 是不变的。这是因为对于一个区间,其 \(gcd\) 的变化种类最多只有其区间最大值的质因数个种类,在 \(10^9\) 内不超过 \(10\) 个。因此,我们考虑维护区间从左端点开始的前缀 \(\gcd\) 数组 \(L\) ,从右端点开始的后缀 \(\gcd\) 数组 \(R\) 。例如, 区间有 \(7\) 个数 \(\{ 24,12,16,6,30,18,9\}\) ,那么其 \(L = \{(24,1),(12,1),(4,1),(2,3),(1,1) \}\) , \(R=\{ (9,2),(3,2),(1,3) \}\) (其中第一个数表示 \(\gcd\) ,第二个数表示持续长度) 。于是,尺取法的端点枚举这两个数字即可,最多移动 \(10^2\) 次。

合并时, \(len,GCD\) 直接求, \(ans\) 等于尺取法的答案再加上 \(GCD\) 和区间 \(GCD\) 一致的左右子区间 \(ans\) 。对于 \(L,R\) ,我们不妨考虑 \(L\) ,首先继承左子区间的 \(L\) ,然后逐步加上右子区间的 \(R\) ,如果要加上的一块是当前 \(L\) 末尾 \(\gcd\) 的倍数则直接加在 \(L\) 末尾的长度上,否则 push_back 一个新元素, \(R\) 同理。

时间复杂度 \(O((n+q) \log n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template<class T>
class SegmentTree {
    int n;
    vector<T> node;

    T query(int rt, int l, int r, int x, int y) {
        if (r < x || y < l) return T();
        if (x <= l && r <= y) return node[rt];
        int mid = l + r >> 1;
        return query(rt << 1, l, mid, x, y) + query(rt << 1 | 1, mid + 1, r, x, y);
    }

public:
    SegmentTree(int _n = 0) { init(_n); }
    SegmentTree(const vector<T> &src) { init(src); }

    void init(int _n = 0) {
        n = _n;
        node.assign(n << 2, T());
    }
    void init(const vector<T> &src) {
        assert(src.size() >= 2);
        init(src.size() - 1);
        function<void(int, int, int)> build = [&](int rt, int l, int r) {
            if (l == r) return node[rt] = src[l], void();
            int mid = l + r >> 1;
            build(rt << 1, l, mid);
            build(rt << 1 | 1, mid + 1, r);
            node[rt] = node[rt << 1] + node[rt << 1 | 1];
        };
        build(1, 1, n);
    }

    T query(int x, int y) { return query(1, 1, n, x, y); }
};
struct T {
    int len = 0;
    int GCD = 0;
    vector<pair<int, int>> L = {}, R = {};
    ll ans = 0;
    friend T operator+(const T &a, const T &b) {
        if (!a.len) return b;
        if (!b.len) return a;

        T x = T();
        x.len = a.len + b.len;
        x.GCD = gcd(a.GCD, b.GCD);
        if (a.GCD == x.GCD) x.ans += a.ans;
        if (b.GCD == x.GCD) x.ans += b.ans;

        int l = a.R.size() - 1, r = 0, sum = 0;
        while (l >= 0) {
            while (r < b.L.size()) {
                if (gcd(a.R[l].first, b.L[r].first) == x.GCD) break;
                sum += b.L[r].second;
                r++;
            }
            x.ans += 1LL * a.R[l].second * (b.len - sum);
            l--;
        }

        x.L = a.L;
        for (int i = 0;i < b.L.size();i++) {
            if (b.L[i].first % x.L.back().first) x.L.push_back({ gcd(x.L.back().first,b.L[i].first),b.L[i].second });
            else x.L.back().second += b.L[i].second;
        }
        x.R = b.R;
        for (int i = 0;i < a.R.size();i++) {
            if (a.R[i].first % x.R.back().first) x.R.push_back({ gcd(a.R[i].first,x.R.back().first),a.R[i].second });
            else x.R.back().second += a.R[i].second;
        }

        return x;
    }
};

bool solve() {
    int n;
    cin >> n;
    vector<T> a(n + 1);
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        a[i] = { 1,x,{{x,1}},{{x,1}},1 };
    }
    SegmentTree<T> sgt(a);

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        auto tar = sgt.query(l, r);
        cout << tar.GCD << ' ' << tar.ans << '\n';
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    for (int i = 1;i <= t;i++) {
        cout << "Case #" << i << ":" << '\n';
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

标签:gcd,int,NC15557,最大公约数,ans,区间,first,GCD
From: https://www.cnblogs.com/BlankYang/p/17369880.html

相关文章

  • 2023-05-03 线性模型与区间DP
    线性模型与区间DP1线性模型基本概念这里的线性是指状态的排布是线性的线性模型是动态规划中最常用的模型一般的代码模型是:for(inti=0;i<n;i++){for(j=0;j<i;j++){//Todo:更新dp的具体逻辑}}最典型的一个例题:最长上升子序列见第......
  • 链表内指定区间反转
    描述将一个节点数为size链表m 位置到 n位置之间的区间反转,要求时间复杂度 O(n),空间复杂度 O(1)。例如:给出的链表为 1→2→3→4→5→NULL, m=2,n=4,返回 1→4→3→2→5→NULL.数据范围: 链表长度 0<size≤1000,0<m≤n≤size,链表中每个节点的值满足∣val∣≤1000要......
  • 2023-05-02:如果一个正整数每一个数位都是 互不相同 的,我们称它是 特殊整数 。 给你一
    2023-05-02:如果一个正整数每一个数位都是互不相同的,我们称它是特殊整数。给你一个正整数n,请你返回区间[1,n]之间特殊整数的数目。输入:n=20。输出:19。答案2023-05-02:可以通过数字组合和状态压缩的动态规划算法来解决。具体过程如下:1.对于给定的正整数n,求出其位数......
  • 区间不同数的个数 二维数点 扫描线 可持久化线段树
    二维数点,对于询问的\([l,r]\)区间我们只需要统计有多少个数上一次出现的位置\(pos\)满足\(pos\leql\),即可。template<classT>structBIT{Tc[N];intsize;voidresize(ints){size=s;}Tquery(intx){//1...xassert(x<=size);......
  • 区间涂色问题
    一眼区间dp设dp[i][j]为涂完i到j所需的最小次数当a[i]==a[j]时,dp[i][j]=min(dp[i+1][j-1]+1,min(dp[i+1][j],dp[i][j-1]));为什么是dp[i+1][j-1]+1,此时会产生一个异想天开的想法,就是取遍历一遍i+1到j-1这一段字符串,看是否有a[i]字符的出现,如果出现的话dp[i][j]=dp[i+1][j......
  • 区间dp 和 树型dp
    区间dp递推方程是以区间的形式给出一般套路:枚举区间长度区间端点区间分界点然后就是想怎么去对这个区间进行一定的操作从最原始的地方开始一步步推导方程!for(i=1;i<n;i++)//区间长度为1{ for(j=1;j<=n-i;j++)//区间开头 { for(k=j;k<j+i;k++)//分界点 { f[j][......
  • 力扣 228. 汇总区间--python
    给定一个 无重复元素的 有序整数数组nums。返回恰好覆盖数组中所有数字的最小有序区间范围列表 。也就是说,nums的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于nums的数字x。列表中的每个区间范围[a,b]应该按如下格式输出:"a->b",如果......
  • 6669: 括号配对 区间dp
    描述 Hecy又接了个新任务:BE处理。BE中有一类被称为GBE。以下是GBE的定义:空表达式是GBE如果表达式A是GBE,则[A]与(A)都是GBE如果A与B都是GBE,那么AB是GBE。 输入 输入仅一行,为字符串BE。对于100%的数据,输入的字符串长度小于100。 输......
  • 区间DP小结(附经典例题) 转载
    区间DP转载自:原博客一、定义​区间DP是线性动态规划的扩展,适用场景为每段区间的最优解可以通过更小区间的最优解得到。所以我们一般的解题思路都是先在小区间得到最优解,然后总结出递推公式,利用小区间的最优解求大区间的最优解。二、实现伪代码//mst(dp,0)初始化dp数组for......
  • 最大公约数学习笔记
    一、定义因数/约数:给定一个正整数\(x\),\(x\)的因数/约数就是所有满足\(x\)是\(y\)的正整数倍的\(y\)。最大公因数/最大公约数:给定两个正整数\(a\),\(b\),求一个最大的正整数数\(x\),使得它同时是\(a\)和\(b\)的因数。一般在OI中记为\((a,b)=x\),在数学上记为\(\gc......