评测记录

// Problem: P9989 [Ynoi Easy Round 2023] TEST_69
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9989
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// Date: 2024/07/25 20:05:00
// Author: Li_Feiy
#include<bits/stdc++.h>
#define arrout(a,n) rep(i,1,n)std::cout<<a[i]<<" "
#define arrin(a,n) rep(i,1,n)a[i]=read()
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dep(i,x,n) for(int i=x;i>=n;i--)
#define erg(i,x) for(int i=head[x];i;i=e[i].nex)
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define mem(a,x) memset(a,x,sizeof a)
#define all(x) x.begin(),x.end()
#define arrall(a,n) a+1,a+1+n
#define PII std::pair<int,int>
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int unsigned int
#define il inline
#define ss second
#define ff first
#define itn int
int read() {
    char ch=getchar();
    int r=0,w=1;
    while(ch<'0'||ch>'9') w=ch=='-'?-1:w,ch=getchar();
    while(ch>='0'&&ch<='9') r=r*10+ch-'0',ch=getchar();
    return r*w;
}
CI N=1e6+5;
int n,m,a[N];
struct SegmentTree {
	int val[N<<2],lcm[N<<2];
	void pushup(int k) {val[k]=val[k<<1]+val[k<<1|1],lcm[k]=std::min((int)1e18,(int)((int)(lcm[k<<1]*lcm[k<<1|1])/std::__gcd(lcm[k<<1],lcm[k<<1|1])));}
	void build(int k,int l,int r) {
		if(l==r) {
			val[k]=lcm[k]=a[l];
			return ;
		}
		int mid=l+r>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
		pushup(k);
	}
	void update(int k,int l,int r,int x,int y,int v) {
		if(y<l||x>r) return ;
		if(v%lcm[k]==0||lcm[k]==1e18) return ;
		if(l==r) {
			val[k]=lcm[k]=std::__gcd(val[k],v);
			return ;
		}
		int mid=l+r>>1;
		if(x<=mid) update(k<<1,l,mid,x,y,v);
		if(y>mid) update(k<<1|1,mid+1,r,x,y,v);
		pushup(k);
	}
	int query(int k,int l,int r,int x,int y) {
		if(y<l||x>r) return 0;
		if(x<=l&&r<=y) return val[k];
		int mid=l+r>>1,ans=0;
		if(x<=mid) ans+=query(k<<1,l,mid,x,y);
		if(y>mid) ans+=query(k<<1|1,mid+1,r,x,y);
		return ans;
	}
}st;
signed main() {
	n=read(),m=read();
	arrin(a,n);
	st.build(1,1,n);
	while(m--) {
		int op=read(),l=read(),r=read();
		if(op==1) {int x=read();st.update(1,1,n,l,r,x);}
		else std::cout<<st.query(1,1,n,l,r)<<"\n";
	}
    return 0;
}