---
title: Codeforce 914 D. Bash and a Tough Math Puzzle 解析(線段樹、數論)
description: "Codeforce 914 D. Bash and a Tough Math Puzzle 解析(線段樹、數論)"
---
<meta name="robots" content="Codeforce 914 D. Bash and a Tough Math Puzzle 解析(線段樹、數論)">
<!-- toc -->

# Codeforce 914 D. Bash and a Tough Math Puzzle 解析(線段樹、數論)
今天我們來看看CF914D
[題目連結](https://codeforces.com/problemset/problem/914/D)

> **題目**
給你一個長度為$n$的數列$a$，每次玩家會選擇一個區間猜$g.c.d.$的值，或者改變數列中的某個數字。而猜中不一定要完全準確，如果玩家能夠改動一個區間中的數字讓$g.c.d.$完全猜中也是可以的。

### 前言
我對線段樹還是不熟阿，一開始一直感覺$g.c.d.$沒辦法用線段樹維護...

### 想法
上模板，從維護區間和的模板改成維護$g.c.d.$(這就是為什麼我code中的元素修改函式叫做$add$)。
接著注意到一件事，猜中的條件是:假設區間中有$k$個數字，只要其中$k-1$個數字可以被$val$($val\stackrel{def}{=}$玩家猜的數字)整除就可以了(如果這$k-1$個數字的$g.c.d.\ge val$，那麼只要把最後那個數字改成$val$就好)。
一開始我就直接這樣實作，每次從$root$開始往下找有幾個數字可以被整除，整個區間都看過以後再來檢查是否$\ge k-1$，但是發現這樣會TLE。
查網路後發現我們必須用一個全域變數去計算:有多少在區間中數字不可被整除，如果發現數量$>1$就要馬上跳離搜尋，如此一來就不會TLE了。
($almost$函式是這題的重點，寫法和模板有點差異，要小心實作。)

### 程式碼:

const int _n=5e5+10;
int n,a[_n],q,tt,tot=0;
namespace Seg{
  int nn;
  int t[_n<<2];
  void pull(int v){t[v]=__gcd(t[2*v+1],t[2*v+2]);}
  void apply(int v, int val){t[v]=val;}
  void build(int v, int l, int r){
    if(l+1==r)t[v]=a[l];
    else{int m=(l+r)>>1;build(2*v+1,l,m),build(2*v+2,m,r);pull(v);}
  }
  void add(int v,int l,int r,int ql,int qr,int val){
    if(r<=ql or qr<=l)return;
    else if(ql<=l and r<=qr)apply(v,val);
    else{
      int m=(l+r)>>1;
      add(2*v+1,l,m,ql,qr,val),add(2*v+2,m,r,ql,qr,val);
      pull(v);
    }
  }
  void add(int pos,ll val){add(0,0,nn,pos,pos+1,val);}
  void init(int n_){nn=n_;build(0,0,nn);}
  void almost(int v,int l,int r,int ql,int qr,int val){
    if(tot>1)return;
    if(r<=ql or qr<=l)return;
    else if(ql<=l and r<=qr and t[v]%val==0)return;
    else{
      if(l+1==r){tot++;return;}
      int m=(l+r)>>1;
      almost(2*v+1,l,m,ql,qr,val),almost(2*v+2,m,r,ql,qr,val);
    }
  }
}
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);
  cin>>n;rep(i,0,n)cin>>a[i]; cin>>q;
  Seg::init(n);
  while(q--){
    cin>>tt;
    if(tt==1){
      int l,r,x;cin>>l>>r>>x;l--,r--;
      tot=0;Seg::almost(0,0,n,l,r+1,x);
      if(tot<=1)cout<<"YES\n";
      else cout<<"NO\n";
    }else{
      int i,y;cin>>i>>y;i--;
      Seg::add(i,y);
    }
  }
  return 0;
}

標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/914/submission/90432062)