分块，跟 P4145 一个思路。

样例过了但 0pts。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,M=5e2+5;
int block,tot,n,m,flag[M],lt[M],rt[M],a[N],belong[N];
unsigned sum[M];
void build(){
	block=(int)sqrt((double)n);
	tot=n/block;
	if(n%block) tot++;
	for(int i=1;i<=tot;i++){
		lt[i]=(i-1)*block+1;
		rt[i]=i*block;
	}
	rt[tot]=n;
	for(int i=1;i<=n;i++){
		belong[i]=(i-1)/block+1;
		sum[belong[i]]+=a[i];
	}
}
void change(int x,int y,int k){
	if(belong[x]==belong[y]){
		if(flag[belong[x]]==1) return;
		for(int i=x;i<=y;i++){
			if(a[i]!=1){
				sum[belong[x]]-=a[i];
				a[i]=__gcd(a[i],k);
				sum[belong[x]]+=a[i];
			}
		}
		return;
	}
	if(flag[belong[x]]!=1) {
		for(int i=x;i<=rt[belong[x]];i++){
			sum[belong[x]]-=a[i];
			a[i]=__gcd(a[i],k);
			sum[belong[x]]+=a[i];
		}
	}
	if(flag[belong[y]]!=1) {
		for(int i=lt[belong[y]];i<=y;i++){
			sum[belong[y]]-=a[i];
			a[i]=__gcd(a[i],k);
			sum[belong[y]]+=a[i];
		}
	}
	for(int i=belong[x]+1;i<=belong[y]-1;i++){
		if(!flag[i]||k%flag[i]){
			flag[i]=__gcd(flag[i],k);
			if(flag[i]!=1){
				for(int j=lt[i];j<=rt[i];j++){
					if(a[j]!=1){
						sum[i]-=a[j];
						a[j]=__gcd(a[j],k);
						sum[i]+=a[j];
					}
				}
			}
		}
	}
	return;
}
unsigned ask(int x,int y){
	unsigned ans=0;
	if(belong[x]==belong[y]){
		if(flag[belong[x]]!=1){
            for(int i=x;i<=y;i++) ans+=a[i];
            return ans;
        }
        else return y-x+1;
	}
	if(flag[belong[x]]!=1)for(int i=x;i<=rt[belong[x]];i++)ans+=a[i];
	else ans+=rt[belong[x]]-x;
	if(flag[belong[x]]!=1)for(int i=lt[belong[y]];i<=y;i++)ans+=a[i];
	else ans+=y-lt[belong[y]];
	for(int i=belong[x]+1;i<=belong[y]-1;i++){
		if(flag[i]!=1) ans+=sum[i];
		else ans+=block;
	}
	return ans;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build();
	for(int i=1;i<=m;i++){
		int opt,l,r;
		cin>>opt>>l>>r;
		if(opt==1){
			int x;
			cin>>x;
			change(l,r,x);
		}
		else{
			cout<<ask(l,r)<<endl;
		}
	}
	return 0;
}