P9989 TEST_69

题面

原题链接 click

题解

经典的，注意到一个数被有效操作 \(O(\log V)\) 次后会变为 \(1\)。
注意到如果 \(a_k|x\)，则这次修改对 \(a_k\) 无效。我们设法只进行有效的修改。
注意到如果 \(\mathrm{lcm}(a_l,a_{l+1},\cdots,a_r)|x\)，则修改对 \(a_l,a_{l+1},\cdots,a_r\) 均无效。
那么我们用线段树维护区间 \(\mathrm{lcm}\)，修改时在线段树上 dfs，遇到无效区间就跳过。
这样，进行一次有效操作用时 \(O(\log n)\)，一共 \(O(n\log V)\) 次有效操作，总复杂度 \(O(n\log V\log n)\)。

Code

#include<bits/stdc++.h>
using namespace std;
const long long MAXLCM=1.5e18;
struct node{
    long long lcm;
    unsigned int sum;
    inline node operator+(const node &b)const{
        node c; c.sum=sum+b.sum;
        long long h=__gcd(b.lcm,lcm);
        if(MAXLCM/(lcm/h)<b.lcm) c.lcm=MAXLCM;
        else c.lcm=lcm/h*b.lcm;
        return c;
    }
};
node s[800005];
void build(int p,int l,int r){
    if(l==r){
        cin>>s[p].lcm; s[p].sum=s[p].lcm; return;
    }
    int m=l+r>>1;
    build(p<<1,l,m); build(p<<1|1,m+1,r); s[p]=s[p<<1]+s[p<<1|1];
}
void update(int p,int l,int r,int x,int y,long long v){
    if(x>r||y<l) return;
    if(v%s[p].lcm==0) return;
    if(l==r){
        s[p].sum=s[p].lcm=__gcd(v,s[p].lcm); return;
    }
    int m=l+r>>1;
    update(p<<1,l,m,x,y,v); update(p<<1|1,m+1,r,x,y,v);
    s[p]=s[p<<1]+s[p<<1|1];
}
unsigned int query(int p,int l,int r,int x,int y){
    if(x>r||y<l) return 0; if(x<=l&&r<=y) return s[p].sum;
    int m=l+r>>1; return query(p<<1,l,m,x,y)+query(p<<1|1,m+1,r,x,y);
}
int n,q;
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>q; build(1,1,n);
    while(q--){
        int tp,l,r; long long x;
        cin>>tp>>l>>r;
        if(tp==1){
            cin>>x; update(1,1,n,l,r,x);
        }else cout<<query(1,1,n,l,r)<<'\n';
    }
    return 0;
}