RT，采用BIT方法

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <queue>

#define endl "\n"
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define R register
//#define int long long
#define LL long long
#define ULL unsigned long long
#define INF 0x3f
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define mid(a, b) (a + b) >> 1 

const int N = 3e5 + 7, M = 1e2 + 9, P = 131, MOD = 1e6 + 7;

using namespace std;//BIT

inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if(c == '-') flag = true;
    else num = c - '0';
    while(isdigit(c = getchar())) num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
} 

int _;

int n, m;

int f[N];

LL tree[N];

#define vit vector <int> :: iterator

vector <int> s[N];
vector <vit> t;

int lowbit(int x)

{
	return x & (-x);
}

LL sum(int x)

{
	LL res = 0;
	while (x) res += tree[x], x -= lowbit(x);
	return res;
}

void add(int x, int v)

{
	while (x <= n) tree[x] += v, x += lowbit(x);
}

void init()

{   
    n = read(), m = read();
    for (R int i = 1; i <= n; ++ i ) 
    {
    	f[i] = read();
    	for (R int j = 1; j * j <= f[i]; ++ j )
    	{
    		if (f[i] % j == 0)
    		{
    			s[j].push_back(i);
    			if (f[i] != j * j) s[f[i] / j].push_back(i);
			}
		}
		add(i, f[i]);
	}
    //memset(f, 0, sizeof f);
}

void solve()

{
    init();

	while (m -- )
	{
		int opt;
		opt = read();
		if (opt == 1)
		{
			int l, r, x;
			l = read(), r = read(), x = read();
			t.clear();
			if (x == 1 || !s[x].size()) continue;
			vit l2 = lower_bound(s[x].begin(), s[x].end(), l);
			vit r2 = upper_bound(s[x].begin(), s[x].end(), r);
			if (l2 == s[x].end()) continue;
			for (vit it = l2; it <= r2; ++ it )
			{
				if (f[*it] % x != 0) continue;
				add(*it, -(f[*it] - f[*it] / x));
				f[*it] /= x;
				if (f[*it] % x != 0) t.push_back(it);
			}
			if(t.size()) 
			{
				for (R int i = t.size() - 1; i >= 0; -- i ) s[x].erase(t[i]);
			}
		}
		else
		{
			int l, r;
			l = read(), r = read();
			cout << sum(r) - sum(l - 1) << endl;
		}
	}
    //puts("");
}

signed main()

{
    IOS;

    _ = 1;
    //t = read();
    while (_ -- ) solve();
}