分析
考虑线段树。
\(20\) 分
统计节点懒标记，在每次询问之前统一下传 \((lst,i-1)\) 的修改懒标记，\(lst\) 是上一次询问的位置。
\(40\) 分
在统一下传的过程中打标记，如果当前节点的某个儿子所在子树中没有需要下传懒标记的节点，则不更新那个儿子的内容。
\(70\) 分
注意到 \(a\) 与 \(x\) 随机生成。再打个标记，记录某个区间元素是否均为 \(1\)。由于 \(\gcd(x,1)=1\)，如果这个区间中元素均为 \(1\)，则不对其懒标记更新。
\(100\) 分
拓展第 \(3\) 个标记。如果对于一些数 \(y_1,y_2,\dots,y_k\) 的最小公倍数 \(l\)，有：\(\gcd(l,x)=l\)，则表示对于任意 \(y_j(1 \le j \le k)\) 都有 \(\gcd(y_j,x)=y_j\)，证明显然。而第 \(3\) 个标记就是相当于使 \(l=1\)，所以直接维护区间最小公倍数，对于 \(\gcd(l,x) \ne l\) 的区间，暴力维护即可。
由于每个 \(a_i\) 被修改的次数不大于 \(\log V\)，复杂度从视数据而定降到 \(O(n\log^2 V)\)（\(\log n\) 和 \(\log V\) 没区别吧）。
注：\(l\) 的值可能会很大。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define lcm(x,y) (__int128)((__int128)(x*y)/__gcd(x,y))
il int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
const int N=2e5+10,p=4294967296;
int n,m,a[N];
struct tree{
int l,r,s;
__int128 lm;
}tr[N<<2];
il void up(int now){
tr[now].s=(tr[now<<1].s+tr[now<<1|1].s)%p,
tr[now].lm=lcm(tr[now<<1].lm,tr[now<<1|1].lm);
}
il void down(int now){
/**/return ;
}
il void insert(int now,int l,int r,int k){
if(tr[now].l==tr[now].r){tr[now].lm=tr[now].s=__gcd(tr[now].s,k);return ;}
int mid=tr[now].l+tr[now].r>>1;
if(l<=mid&&((__int128)(k)%tr[now<<1].lm)) insert(now<<1,l,r,k);
if(mid<r&&((__int128)(k)%tr[now<<1|1].lm)) insert(now<<1|1,l,r,k);
up(now);
return ;
}
il void upd(int now){
/**/return ;
}
il int query(int now,int l,int r){
if(tr[now].l>=l&&tr[now].r<=r){return tr[now].s;}
int ans=0;
int mid=tr[now].l+tr[now].r>>1;
if(l<=mid) ans=(ans+query(now<<1,l,r))%p;
if(mid<r) ans=(ans+query(now<<1|1,l,r))%p;
return ans;
}
il void build(int now,int l,int r){
tr[now].l=l,tr[now].r=r;
if(l==r){tr[now].lm=tr[now].s=a[l];return ;}
int mid=l+r>>1;build(now<<1,l,mid),build(now<<1|1,mid+1,r);
up(now);return ;
}
il void solve(){
n=read(),m=read();
for(re int i=1;i<=n;++i) a[i]=read();
build(1,1,n);
for(re int i=1;i<=m;++i){
int op,l,r,x;op=read(),l=read(),r=read();
if(op==1) insert(1,l,r,read());
else cout<<query(1,l,r)<<"\n";
}
return ;
}
signed main(){
solve();
return 0;
}