不......不会吧/jk/jk

虽然卡常，但也不至于全 T 啊/jk/jk

放 IDE 上跑了一下，样例都会 T 掉/kk

求调一下/kel

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<iostream>

#define MAXN 100005
#define LL long long
#define RE register

using namespace std;

inline LL qread(){
	RE char ch=getchar();
	RE LL x=0,f=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-48;
		ch=getchar();
	}
	return x*f;
}

int a[MAXN];
int n,m;
LL c[MAXN];
vector<int>it[500005];//每个数的倍数

vector<int>fa[500005];
inline int find(int x,int v){
	if(v==fa[x].size()||v==fa[x][v])return (v);
	return (fa[x][v]=find(x,fa[x][v]));
}//冰茶姬

struct BIT{
	inline int lowbit(int x){
		return x&(-x);
	}
	
	inline void modify(int x,LL k){
		for(RE int i=x;i<=n;i+=lowbit(i)){
			c[x]+=k;
		}
	}
	
	inline LL Sum(int x){
		LL ans=0;
		for(RE int i=x;i>=0;i-=lowbit(i)){
			ans+=c[i];
		}
		return ans;
	}
};//树状数组
BIT tree;

inline void pre(){
	n=qread();
	m=qread();
	for(RE int i=1;i<=n;i++){
		a[i]=qread();
		tree.modify(i,a[i]);
	}
	for(RE int i=1;i<=n;i++){
		for(RE int j=1;j*j<=a[i];j++){
			if(a[i]%j==0){
				it[j].push_back(i);
				fa[j].push_back(fa[j].size());
				if(j*j!=a[i]){
					it[a[i]/j].push_back(i);
					fa[a[i]/j].push_back(fa[a[i]/j].size());
				}
			}
            //处理每个数的约数
		}
	}
}

inline void change(int l,int r,int x){
	int pos=find(x,lower_bound(it[x].begin(),it[x].end(),l)-it[x].begin());
	while(pos<it[x].size()&&it[x][pos]<=r){
		int u=it[x][pos];
		if(a[u]%x==0){
			tree.modify(u,a[u]/x-a[u]);
			a[u]/=x;
		}
		if(a[u]%x!=0)fa[x][pos]=pos+1;
		pos=find(x,pos+1);
	}
}

int main(void){
	
	pre();
	LL ans=0;
	while(m--){
		int op,l,r;
		op=qread();
		l=qread()^ans;
		r=qread()^ans;
		if(l>=r)swap(l,r);
		if(op==1){
			LL x=qread()^ans;
			if(x==1)continue;
			change(l,r,x);
		}
		else{
			ans=tree.Sum(r)-tree.Sum(l-1);
			printf("%lld\n",ans);
		}
	}
	
	return 0;
}