学习珂学的最好方法是

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int maxn=1e5+10,maxm=5e7+10,mod=1e9+7;
inline int read(){
	int c,w=0,n=0;
	while((c=getchar())<'0'||'9'<c) w=c=='-';
	do n=n*10+c-'0';while('0'<=(c=getchar())&&c<='9');
	return w?-n:n;
}
int write(int n){
	if(n<0) putchar('-'),n=-n;
	if(n>9) write(n/10);
	putchar(n%10+'0');
	return n;
}

int n,m,tot,tmpt,a[maxn],t[maxn],root[maxn*5],tmp[maxn],dt[maxm],val[maxm],l[maxm],r[maxm];
inline int newnode(int x){return dt[++tot]=x,val[tot]=rand(),tot;}
int merge(int x,int y){return x&&y?val[x]>val[y]?r[x]=merge(r[x],y),x:(l[y]=merge(x,l[y]),y):x+y;}
void split(int p,int v,int &x,int &y){
	if(!(bool)p) return (void)(x=y=0);
	if(dt[p]<=v) x=p,split(r[p],v,r[p],y);
	else y=p,split(l[p],v,x,l[p]);
}
int build(int lq,int rq){
	if(lq>rq) return 0;
	if(lq==rq) return newnode(tmp[lq]);
	int mid=lq+rq>>1,p=newnode(p);
	return l[p]=build(lq,mid-1),r[p]=build(mid+1,rq),p;
}
void get(int x){
	if(l[x]) get(l[x]);
	tmp[++tmpt]=dt[x];
	if(r[x]) get(r[x]);
}
void midfor(int x){/*debug*/
	if(l[x]) midfor(l[x]);
	cout<<dt[x]<<" ";
	if(r[x]) midfor(r[x]);
}

signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
		for(int j=i;j<=n;j+=j&-j) t[j]+=a[i];
		for(int j=1;j*j<=a[i];++j) if(a[i]%j==0){
			root[j]=merge(root[j],newnode(i));
			if(j*j!=a[i]) root[a[i]/j]=merge(root[a[i]/j],newnode(i));
		}
	}
	for(int o=1;o<=m;++o){
		int opt=read(),l=read(),r=read();
		if(opt==1){
			int x=read(),s1,s2,s3;
			split(root[x],r,s2,s3),split(s2,l-1,s1,s2),tmpt=0;
			if(s2) get(s2),s2=0;
			for(int i=1;i<=tmpt;++i){
				if(a[tmp[i]]%x) continue;
				a[tmp[i]]/=x;
				for(int j=tmp[i],k=a[tmp[i]]*(x-1);j<=n;j+=j&-j) t[j]-=k;
				if(a[tmp[i]]%x==0) tmp[++s2]=tmp[i];
			}
			if(s2) s2=build(1,s2);
			root[x]=merge(s1,merge(s2,s3));
		}
		else{
			int ans=0;
			for(int i=r;i;i-=i&-i) ans+=t[i];
			for(int i=l-1;i;i-=i&-i) ans-=t[i];
			write(ans),puts("");
		}
	}
	return 0;
}