题目分析：
考虑对于一次修改至少会让 \(x\) 变成 \(\frac{x}{2}\) 所以对于每一个数最多被操作 \(\log{n}\) 次，那么直接暴力操作就好了。
所以其实关键问题是每次怎么找到哪些数是需要被操作的。
看到值域那么小，不难想到可以直接维护 \(f[i]\) 表示 \(i\) 的倍数的数的集合，这样的话直接从这上面找就好了。但是这样还是不行，因为一次操作还是有可能被卡成 \(O(n)\)，那么其实就是说我们要做到将已经不是 \(i\) 的倍数的数在访问的时候直接跳过，也就是用类似并查集维护连续段的手段啊。
也就是记 \(p[i][j]\) 表示 \(i\) 的倍数的数里第 \(j\) 个数开始向右第一个仍是 \(i\) 的倍数的数是哪个位置，然后删除就直接并查集的合并就可以了。
对于区间和就直接上树状数组就可以简单维护了。
代码：
因为这个题极致卡常，我没卡过去，所以这个代码过不去的。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5+5;
int n,a[N];
ll sum[N];
vector<int> f[N],p[N];
inline long long read(){
long long x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int find(int x,int y){
if(y == (int)p[x].size()) return y;
if(p[x][y] == y) return y;
return p[x][y] = find(x,p[x][y]);
}
void modify(int x,int y){
for(int i=x; i<=n; i+=i&(-i)) sum[i] += y;
}
ll query(int x){
ll ans = 0;
for(int i=x; i; i-=i&(-i)) ans += sum[i];
return ans;
}
signed main(){
int m;n=read();m=read();
for(int i=1; i<=n; i++){
a[i]=read();
for(int j=1; j*j<=a[i]; j++){ //预处理
if(a[i] % j == 0){
f[j].push_back(i); //f 为具体位置
p[j].push_back(p[j].size()); //g 表示这个位置的下一个合法的位置
if(j * j != a[i]){
f[a[i]/j].push_back(i);
p[a[i]/j].push_back(p[a[i]/j].size());
}
}
}
modify(i,a[i]);
}
ll lst = 0;
for(int i=1; i<=m; i++){
ll opt,l,r,x;opt=read();l=read();r=read();
l ^= lst;r ^= lst;
if(opt == 1){
x=read();
x ^= lst;
if(x == 1) continue;
int tmp = lower_bound(f[x].begin(),f[x].end(),l) - f[x].begin();
for(int i=find(x,tmp);i<(int)f[x].size() && f[x][i]<=r;i=find(x,i+1)){ //并查集维护连续段
if(a[f[x][i]] % x == 0){
modify(f[x][i],-a[f[x][i]]);
modify(f[x][i],a[f[x][i]]/x);
a[f[x][i]]/=x;
}
if(a[f[x][i]] % x != 0) p[x][i] = i+1;
}
}
else printf("%lld\n",lst = (query(r) - query(l-1)));
}
return 0;
}