Link

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 300005;
const int mod = (1ll << 32);
const int INF = 3e18;
int a[N];

namespace SegTree{
	int gcd_(int x,int y){
		if(!y) return x;
		return gcd_(y,x % y);
	}
	
	int lcm_(int x,int y){
		__int128 lcm = (__int128)x * y / gcd_(x,y);
		if(lcm > INF) return INF;
		return lcm;
	}
	
	#define l(p) t[(p)].l
	#define r(p) t[(p)].r
	#define lcm(p) t[(p)].lcm
	#define sum(p) t[(p)].sum
	#define len(p) ((r(p)) - (l(p)) + 1)
	#define lc(p) ((p) << 1)
	#define rc(p) ((p) << 1 | 1)
	struct node{
		int l;
		int r;
		int lcm;
		int sum;
	}t[N << 2];
	
	void push_up(int p){
		lcm(p) = lcm_(lcm(lc(p)),lcm(rc(p)));
		sum(p) = (sum(lc(p)) % mod + sum(rc(p)) % mod) % mod;
	}
	
	void build(int p,int l,int r){
		l(p) = l;
		r(p) = r;
		if(l == r){
			sum(p) = a[l] % mod;
			lcm(p) = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(lc(p),l,mid);
		build(rc(p),mid + 1,r);
		push_up(p);
	}
	
	void change(int p,int l,int r,int d){
		if(lcm(p) != -1 && d % lcm(p) == 0) return;
		if(l(p) == r(p)){
			sum(p) = gcd_(sum(p),d);
			lcm(p) = sum(p);
			sum(p) %= mod;
			return;
		} 
		int mid = (l(p) + r(p)) >> 1;
		if(l <= mid) change(lc(p),l,r,d);
		if(r > mid) change(rc(p),l,r,d);
		push_up(p);
	}
	
	int query(int p,int l,int r){
		if(l <= l(p) && r >= r(p)) return sum(p);
		int ans = 0;
		int mid = (l(p) + r(p)) >> 1;
		if(l <= mid) ans = (ans + query(lc(p),l,r)) % mod;
		if(r > mid) ans = (ans + query(rc(p),l,r)) % mod;
		return ans;
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i = 1;i <= n;++ i) cin>>a[i];
	SegTree::build(1,1,n);
	while(m --){
		int op,l,r,x;
		cin>>op;
		if(op == 1){
			cin>>l>>r>>x;
			SegTree::change(1,l,r,x);
		}
		else{
			cin>>l>>r;
			cout<<SegTree::query(1,l,r) % mod<<"\n";
		}
	}
	return 0;
}