RT，卡了好久，但是还是在60-62分（C++98 O2）

#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
//#include<iostream>
using namespace std;
typedef long long ll;
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
//Withers AK ACM;
//#define int long long
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Tree;
int n,m,w,x,y,z,l,r;
static char buf[1<<17],*paa=buf,*pddd=buf;
static char buf2[1<<17],*pppp=buf2;
#define getchar() paa==pddd&&(pddd=(paa=buf)+fread(buf,1,1<<17,stdin),paa==pddd)?EOF:*paa++
inline void pc(char ch){
	if(pppp-buf2==1<<17) fwrite(buf2,1,1<<17,stdout),pppp=buf2;
	*pppp++=ch;
}
inline void pcc(){
	fwrite(buf2,1,pppp-buf2,stdout);
	pppp=buf2;
}
inline void read(int &n){
	int w=1;
	register int x(0);register char c(getchar());
	while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	n=w*x;return;
}
inline void write(ll x){
	if(x<0) pc('-'),x=-x;
	static int sta[20];int top=0;
	do{sta[top++]=x%10,x/=10;}while(x);
	while(top) pc(sta[--top]+48);
}
inline void we(int x){
	write(x);
	pc('\n');
}
inline void ws(int x){
	write(x);
	pc(' ');
}
#define rd read
#define R register 
basic_string<int> g[500010],f[500010];
ll c[100010];
int a[100010];
basic_string<int> cnt[500010];
inline int find(const int now,const int x)
{
	if(x==f[now].size()) return x;
	else if(f[now][x]==x) return x;
	else return f[now][x]=find(now,f[now][x]);
}
inline void add(const int x,const ll y)
{
	for(int i=(x);i<=n;i+=i&(-i))
	{
		c[i]+=y;
	}
	return;
}
inline ll query(const int x)
{
	ll ans=0;
	for(int i(x);i;i-=i&(-i))
	{
		ans+=c[i];
	}
	return ans;
}
ll lst=0;
int maxx=-1;
signed main()
{
	rd(n);rd(m);
	//cnt=eu(500000);
	for(R int i(1);i<=n;++i) rd(a[i]),add(i,a[i]),maxx=max(maxx,a[i]),cnt[a[i]].push_back(i);
	for(R int i(2);i<=maxx;++i)
	{
		for(R int j(i);j<=maxx;j+=i)
		{
			const R int tmp(cnt[j].size());
			for(R int k(0);k<tmp;++k)
			{
				R int kk(cnt[j][k]);
				g[i].push_back(kk);
			}
		}
		if(g[i].size()) sort(g[i].begin(),g[i].end());
	}
	for(R int i(1);i<=maxx;++i)
	{
		R int tmp=g[i].size();
		for(R int j(0);j<tmp;++j)
		{
			f[i].push_back(j);
		}
	}
	while(m--)
	{
		//cerr<<"wqwq"<<'\n';
		R int i,u,v;
		rd(u);
		if(u==1)
		{
			rd(l);rd(r);rd(x);
			l^=lst,r^=lst,x^=lst;
			//cerr<<l<<" "<<r<<" "<<x<<'\n';
			if(x==1||g[x].empty()) continue;
			v=lower_bound(g[x].begin(),g[x].end(),l)-g[x].begin();
			w=upper_bound(g[x].begin(),g[x].end(),r)-g[x].begin()-1;
			//cerr<<"qwq"<<x<<" "<<v<<" "<<g[x].size()<<'\n';
			i=find(x,v);
			while(1)
			{
				if(i>=g[x].size()||i>w) break;
				if(a[g[x][i]]%x==0)
				{
					R int tmp=a[g[x][i]];
					a[g[x][i]]/=x;
					add(g[x][i],tmp/x-tmp);
				}
				else f[x][i]=i+1;
				i=find(x,i+1);
				//cout<<i<<endl;
			}
		}
		else
		{
			rd(l);rd(r);
			l^=lst,r^=lst;
			write(lst=query(r)-query(l-1));
			pc('\n');
		}
	}
	pcc();
}
// POWERED BY WITHERS
// THINK ONCE, CODE TWICE