已经卡了将近两个小时，交了40+发，换成调和级数筛了，但还是只有46分

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,m,a[100005],maxx;
ll tree[100005];
vector<int>fac[500005],pos[500005],cnt[500005];
inline int read()
{
	int ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		ans=(ans<<3)+(ans<<1)+(c^48);
		c=getchar();
	}
	return ans*f;
}
void update(int x,int k)
{
	while(x<=n)
	{
		tree[x]+=k;
		x+=x&(-x);
	}
	return;
}
ll query(int x)
{
	ll sum=0;
	while(x)
	{
		sum+=tree[x];
		x-=x&(-x);
	}
	return sum;
}
int find(int x,int u)
{
	if(u==pos[x].size()) return u;
	return pos[x][u]==u?u:find(x,pos[x][u]);
}
int main()
{
    n=read(),m=read();
	for(register int i=1;i<=n;i++)
	{
		a[i]=read();
		update(i,a[i]);
        maxx=max(maxx,a[i]);
        cnt[a[i]].push_back(i);
	}
    for(register int i=2;i<=maxx;i++)
    {
        for(register int j=i;j<=maxx;j+=i)
        {
            for(register int k=0;k<cnt[j].size();k++)
            {
                fac[i].push_back(cnt[j][k]);
            }
        }
        if(fac[i].size()&&!is_sorted(fac[i].begin(),fac[i].end())) sort(fac[i].begin(),fac[i].end());
    }
    for(register int i=1;i<=maxx;i++)
    {
        for(register int j=0;j<fac[i].size();j++)
        {
            pos[i].push_back(j);
        }
    }
    ll lastans=0;
	while(m--)
	{
		register const int opt=read(),l=read()^lastans,r=read()^lastans;
		if(opt==1)
		{
            register const int x=read()^lastans;
			if(x==1||fac[x].empty()) continue;
			register const int u=lower_bound(fac[x].begin(),fac[x].end(),l)-fac[x].begin(),v=upper_bound(fac[x].begin(),fac[x].end(),r)-fac[x].begin()-1;
            register int i=find(x,u);
            while(1)
			{
                if(i>=fac[x].size()||i>v) break;
				int now=fac[x][i];
				if(a[now]%x==0)
				{
					update(now,a[now]/x-a[now]);
					a[now]/=x;
				}
				else pos[x][i]=i+1;
                i=find(x,i+1);
			}
			continue;
		}
		printf("%lld\n",lastans=query(r)-query(l-1));
	}
	return 0;
}