Acwing-246. 区间最大公约数

本蒟蒻的第二篇题解qwq.

题目大意:

给定一个长度为 \(N\) 的数组,需要在数组上进行两种操作:

1.C l r d,表示把 \(A[l],A[l+1],…,A[r]\) 都加上 \(d\).

2.Q l r,表示询问 \(A[l],A[l+1],…,A[r]\) 的最大公约数 \((GCD)\).

错误解法:

如果你是一个只会打暴力的小蒟蒻(就像我),看到题目后,是不是就只能无奈的打开 IDE,
打起暴力代码了吗?拜托,那可是暴力啊,数据这么大,你怎么能这么暴力地对待他呢

数据:必须的啊,你一个 \(O(nm)\) 复杂度的代码,我可是至高无上的 \(10^{10}\),是能这么对待我的吗?

蒟蒻:啊!!!气死我了,不写了!

所以上面这段对话告诉我们不要轻易惹怒一个蒟蒻qwq

标准解法+证明过程:

在点进这道题之前,先问一句话,知道什么是欧几里德算法吗?

什么,你不知道?那还不快去 这篇网站 补一下.

那么现在,你需要知道一个特性,一个关于欧几里德算法的一个特性:

  • \(\forall a,b\in N,a\le b\Longrightarrow gcd(a,b) = gcd(a,b – a)\)

什么,你说你不相信?那我们不妨来证明一下:

\(x,y \in N,d = gcd(x,y)\), \(d_1 = \frac{x}{d},d_2 = \frac{y}{d}\),则 \(d_1 \perp d_2\).

  1. 假设 \(x = y\),则 \(gcd(x,y) = gcd(x,0) = gcd(x,y – x)\).

  2. 假设 \(x < y,d_3 = \frac{x}{d},d_4 = \frac{y – x}{d}\).

  • \(d_3 = \frac{x}{d} = d_1\).

  • \(d_4 = \frac{y – x}{d} = \frac{d_2 \cdot d – d_1 \cdot d}{d} = \frac{d \cdot (d_2 – d_1)}{d} = (d_2 – d_1)\)

    \(m = gcd(d_1,d_2 – d_1),a = \frac{d_1}{m},b = \frac{d_2 – d_1}{m}\).

    假设 \(m > 1\),那么:
    \(d_1 = m \cdot a,d_2 – d_1 = m \cdot b\)
    \(d_2 = (a + b) \cdot m\)

因为 \(m > 1\),所以 \(d_1 \perp d_2\) 为假,与前者产生矛盾.

综上所述,最终得出 \(gcd(x,y) = gcd(x,y – x)\) 为真.

没错,就证明完了.

而根据数学归纳法,我们又能推出下面的式子:

  • \(gcd(x,y,z) = gcd(x,gcd(y,z)) = gcd(x,gcd(y,z – y)) = gcd(x,y,z – y) = gcd(gcd(x,y),z – y) = gcd(gcd(x,y – x),z – y) = gcd(x,y – x,z – y)\).

  • \(gcd(a_1,a_2,…,a_n) = … = gcd(a_1,a_2 – a_1,…,a_n – a_{n – 1})\)

看到这个结构是不是很熟悉?没错,这不就是差分吗!

于是这道题就很明显了,维护一个差分数组,区间修改则改为了单点修改,查询就…就什么?

额…好像还是要遍历整个区间吧…

这个时候,就得请出我们的线段树了!!

没错,以查询和修改区间为名,与这道题可谓是天造地设,只需要让 \(tree\) 节点存储当前区间的 最大公约数,那区间查询 \(GCD\) 不绰绰有余了?

不过,式子中的 \(a_1\) 该怎么办?

这个时候,\(tree\)还有一个东西要存,那就是当前区间之和.还记得差分的性质吗?

  • \(a_n = b_0 + b_1 + b_2,…, + b_n\)

这不就退化成了前缀和吗?

好了,废话不多说,上代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
  ll l,r;
  ll v,d;
}tree[2000005];
char c;
ll a[500005],b[500005],n,m,u,v,w;
inline ll lu(ll u){return u << 1;}
inline ll ru(ll u){return u << 1 | 1;}
ll gcd(ll a,ll b){
  if(b == 0) return a; 
  else return gcd(b,a % b);
}
void push_up(ll u){
  tree[u].v = tree[lu(u)].v + tree[ru(u)].v;
  tree[u].d = gcd(tree[lu(u)].d,tree[ru(u)].d);
}
void build(ll u,ll l,ll r){
  tree[u].l = l,tree[u].r = r;
  if(l == r){
      tree[u].v = b[l],tree[u].d = b[l];
      return;
  }else{
      ll mid = (l + r) >> 1;
      build(lu(u),l,mid);
      build(ru(u),mid + 1,r);
      push_up(u);
  }
}
void update(ll u,ll f,ll w){
  if(tree[u].l == f && tree[u].r == f){
      tree[u].d += w,tree[u].v += w;return;
  }else{
      ll mid = (tree[u].l + tree[u].r) >> 1;
      if(f <= mid) update(lu(u),f,w);
      if(f > mid) update(ru(u),f,w);
      push_up(u);
      return;
  }
}
ll query(ll u,ll ml,ll mr){ 
  if(tree[u].l >= ml && mr >= tree[u].r) return abs(tree[u].d);
  ll mid = (tree[u].l + tree[u].r) >> 1,res = 0;
  if(ml <= mid) res = gcd(res,query(lu(u),ml,mr));
  if(mr > mid) res = gcd(res,query(ru(u),ml,mr));
  return res;
}
ll query2(ll u,ll ml,ll mr){ // 求前缀和
  if(tree[u].l >= ml && tree[u].r <= mr) return tree[u].v;
  ll mid = (tree[u].l + tree[u].r) >> 1,res = 0;
  if(ml <= mid) res += query2(lu(u),ml,mr);
  if(mr > mid) res += query2(ru(u),ml,mr);
  return res;
}
int main(){
  ios::sync_with_stdio(false);//加快读入速度
  cin >> n >> m;
  for(ll i = 1;i <= n;i++){
      cin >> a[i];
      b[i] = a[i] - a[i - 1];//b为差分数组
  }
  build(1,1,n);
  while(m--){
      cin >> c;
      if(c == 'C'){
          cin >> u >> v >> w;
          update(1,u,w);
          if(v + 1 <= n) update(1,v + 1,w * -1);//防止单点修改时越界
      }else{
          cin >> u >> v;
          if(u == v){
              cout<<query2(1,1,u)<<'\n';
          }else{
              ll tmp = abs(query2(1,1,u));
              cout<<gcd(tmp,query(1,u + 1,v))<<'\n';//当区间只有一个元素时,答案为al
          }
      }
  }
  return 0;
}

这次写的有些急,有问题还请多多指出,谢谢!qwq

请登录后发表评论

    没有回复内容