rt

C++代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,l[100001]={0},r[100001]={0},pos[100001]={0},a[100001]={0};
long long sum[100001]={0},add[100001]={0},cnt[401][500001]={0};
void build(){
	int t=sqrt(n*1.0),num=n/t;
	if(n%t>0) num++;
	for(int i=1;i<=num;i++){
		l[i]=(i-1)*t+1;
		r[i]=i*t;
	}
	r[num]=n;
	for(int i=1;i<=num;i++){
		for(int j=l[i];j<=r[i];j++){
			pos[j]=i;
			sum[i]+=a[j];
			int w=sqrt(a[j]);
			for(int k=1;k<=w;k++){
				if(a[j]%k==0){
					cnt[i][k]+=a[j]-a[j]/k;
					cnt[i][a[j]/k]+=a[j]-k;
					if(k==a[j]/k) cnt[i][k]-=a[j]-a[j]/k;
				}
			}
		}
	}
}
void change(int x,int y,int z){
	int p=pos[x],q=pos[y];
	if(p==q){
		for(int i=x;i<=y;i++) if(a[i]%z==0){a[i]/=z,sum[p]-=a[i]*(z-1);}
	}else{
		for(int i=p+1;i<=q-1;i++) add[i]-=cnt[i][z];
		for(int i=x;i<=r[p];i++) if(a[i]%z==0){a[i]/=z,sum[p]-=a[i]*(z-1);}
		for(int i=l[q];i<=y;i++) if(a[i]%z==0){a[i]/=z,sum[q]-=a[i]*(z-1);}
	}
}
long long query(int x,int y){
	int p=pos[x],q=pos[y];
	long long ans=0;
	if(p==q){
		for(int i=x;i<=y;i++) ans+=a[i];
		ans+=add[p];
	}else{
		for(int i=p+1;i<=q-1;i++) ans+=sum[i]+add[i];
		for(int i=x;i<=r[p];i++) ans+=a[i];
		ans+=add[p];
		for(int i=l[q];i<=y;i++) ans+=a[i];
		ans+=add[q];
	}
	return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build();
    for(int i=1;i<=m;i++){
    	int x,y,z,k;
        scanf("%d%d%d",&x,&y,&z);
        if(x==1){
        	scanf("%d",&k);
        	change(y,z,k);
        }else printf("%lld\n",query(y,z));
    }
    return 0;
}