914D 题解

D. Bash and a Tough Math Puzzle

思路

至多修改一个数，使得 \(\gcd(a_l,a_{l+1},\cdots,a_r)=x\) 。

那么 \([a_l,a_{l+1},\cdots,a_r]\) 至多修改一个数后，中的每一个数都可以被 \(x\) 整除。

就是在问是否只有一个数或没有数不能被 \(x\) 整除。

设 \(cnt\) 为为区间内不能被 \(x\) 整除的数的个数。

1. \(cnt=0\) 可以随意修改任意一个数为 \(x\)

2. \(cnt=1\) 将不能被 \(x\) 整除的数字改为 \(x\)

3. \(cnt\ge2\) 至多修改一个数也不能使 \(\gcd(a_l,a_{l+1},\cdots,a_r)=x\)

代码实现

我们可以考虑使用线段树，用线段树维护区间 \(gcd\)。

如果一段区间的 \(gcd\) 都能整除 \(x\)，那么这段区间的所有数也都能整除 \(x\)。

• 对于操作 \(1\)

递归到当前节点的时候如果当前节点不能被x整除，cnt++。

而且在递归时只要 \(cnt\ge2\) 就停止递归。

• 对于操作 \(2\)

直接进行单点修改，然后向父节点更新区间 \(gcd\)

#include <bits/stdc++.h>
const int N=5e5+5;
int n,q,cnt,seg[N<<2];
int gcd(int x,int y) {
    return y?gcd(y,x%y):x;
}
void pushup(int rt) {
    seg[rt]=gcd(seg[rt*2],seg[rt*2+1]);
}
void build(int rt,int l,int r) {
    if(l==r) {
        scanf("%d",&seg[rt]);
        return;
    }
    int mid=(l+r)>>1;
    build(rt*2,l,mid);
    build(rt*2+1,mid+1,r);
    pushup(rt);
}
void modify(int x,int rt,int l,int r,int val) {
    if(l==r) {
        seg[rt]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(x,rt*2,l,mid,val);
    else modify(x,rt*2+1,mid+1,r,val);
    pushup(rt);
}
void query(int x,int y,int rt,int l,int r,int d) {
    if(cnt>1) return;
    if(l==r) {
        ++cnt;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid&&seg[rt*2]%d) query(x,y,rt*2,l,mid,d);
    if(mid<y&&seg[rt*2+1]%d) query(x,y,rt*2+1,mid+1,r,d);
}
int main(void) {
    scanf("%d",&n);
    build(1,1,n);
    scanf("%d",&q);
    while(q--) {
        int opt;
        scanf("%d",&opt);
        if(opt==1) {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            cnt=0,query(l,r,1,1,n,x);
            puts(cnt>1?"NO":"YES");
        } else {
            int x,k;
            scanf("%d%d",&x,&k);
            modify(x,1,1,n,k);
        }
    }
    return 0;
}