RT
手写的splay，自顶向下的。

#include <bits/stdc++.h>
using namespace std;

#define lowbit(x) ((x) & (-(x))) 

const int maxn = 5e5 + 5;

#define ls son[0]
#define rs son[1]

struct node; 
typedef node* pos;
struct node {
	int val;
	pos son[2];
	node() { val = 0; ls = rs = NULL; }
}; 
node buf[52000000];
pos need_work[maxn];
int buf_cnt, work_cnt;

inline pos new_node(int val) { 
	pos res = buf + (++buf_cnt); 
	res -> ls = res -> rs = buf; 
	res -> val = val;
	return res;
}
template <class T> 
inline void read(T &r) {
	char ch = getchar(); r = 0;
	while (ch < 48 || ch > 57) ch = getchar();
	while (ch > 47 && ch < 58) { r = (r << 1) + (r << 3) + ch - 48; ch = getchar(); }
}
static int _tmp_write[22] = {0}, _cnt_write = 0;
template <class T> 
inline void write(T _w, char _end) {
    if (_w == 0) { putchar(48); return; } _cnt_write = 0;
    while (_w) { _tmp_write[_cnt_write++] = _w % 10 + 48; _w /= 10; }
    while (_cnt_write) putchar(_tmp_write[--_cnt_write]);
    putchar(_end);
}

int n, m, op, l, r, tmp;
int a[maxn];
long long f[maxn], res;

inline void update(int pos, int x) {
	while (pos <= n) {
		f[pos] += x;
		pos += lowbit(pos);
	}
}
inline long long ask(int pos) {
	res = 0;
	while (pos > 0) {
		res += f[pos];
		pos -= lowbit(pos);
	}
	return res;
}

class splay_tree {
private:
	pos root;
public:
	splay_tree() { root = buf; root = __insert(0, root); root = __insert(500001, root); }
	inline void insert(int val) { root = __insert(val, root); }
	inline void remove(int val) { root = __remove(val, root); }
	inline void debug() {
		putchar('\n');
		printf("root: %d\n", root - buf);
		for (int i = 0; i <= buf_cnt; i++) {
			printf("node#%d  val: %d ls: %d rs: %d\n", i, buf[i].val, buf[i].ls - buf, buf[i].rs - buf);
		}
		putchar('\n');
	}
	inline int pre(int val) {
		pos t = root;
	    int ans;
		while (t != buf) {
			if (t -> val < val) {
				ans = t -> val;
				t = t -> rs;
			}
			else t = t -> ls;
		}
		return ans;
	}
	inline int nxt(int val) {
		pos t = root;
	    int ans;
		while (t != buf) {
			if (t -> val > val) {
				ans = t -> val;
				t = t -> ls;
			}
			else t = t -> rs;
		}
		return ans;
	}
	inline void work(int l, int r, int tmp) {
		root = splay(pre(l), root);
		root -> rs = splay(nxt(r), root -> rs);
		work_cnt = 0;
		__work(root -> rs -> ls, tmp);
		root -> rs -> ls = __rebuild(1, work_cnt);
	}
private:
	void __work(pos p, int &tmp) {
		if (p == buf) return;
		__work(p -> ls, tmp);
		if (a[p -> val] % tmp == 0) {
			a[p -> val] /= tmp;
			update(p -> val, a[p -> val] * (1 - tmp));
			if (a[p -> val] % tmp == 0) need_work[++work_cnt] = p;
		}
		__work(p -> rs, tmp);
	}
	pos __rebuild(int l, int r) {
		if (l > r) return buf;
		int mid = (l + r) >> 1;
		need_work[mid] -> ls = __rebuild(l, mid - 1);
		need_work[mid] -> rs = __rebuild(mid + 1, r);
		return need_work[mid]; 
	}
	inline pos rotate(pos x, int with) {
		pos y = x -> son[with];
		x -> son[with] = y -> son[with ^ 1]; y -> son[with ^ 1] = x;
		return y;
	}
	inline pos splay(int val, pos t) {
		node header; header.ls = header.rs = buf;
		pos tmp[2] = {&header, &header}; 
		while (t -> val != val) {
			int f1 = (val > t -> val);
			if (t -> son[f1] == buf) break;
			if (t -> son[f1] -> val != val) {
				int f2 = (val > t -> son[f1] -> val); 
				if (f1 == f2) t = rotate(t, f1);
				if (t -> son[f1] == buf) break;
			}
			tmp[f1 ^ 1] -> son[f1] = t;
			tmp[f1 ^ 1] = t;
			t = t -> son[f1];
		}
		tmp[0] -> rs = t -> ls; tmp[1] -> ls = t -> rs;
		t -> ls = header.rs; t -> rs = header.ls;
		return t;
	}
	inline pos __insert(int val, pos t) {
		pos p = new_node(val);
		if (t == buf) t = p;
		else {
			t = splay(val, t);
			if (t -> val == val) {
				buf_cnt--;
				return t;
			}
			int f = (val > t -> val); 
			p -> son[f] = t -> son[f]; p -> son[f ^ 1] = t; t -> son[f] = buf;
			t = p;
		}
		return t;
	}
	inline pos __remove(int val, pos t) {
		if (t != buf) {
			t = splay(val, t);
			if (val == t -> val) {
				pos p;
				if (t -> ls == buf) p = t -> rs;
				else {
					p = t -> ls;
					p = splay(val, p);
					p -> rs = t -> rs;
				}
				t -> ls = t -> rs = buf;
				t = p;
			}
		}
		return t;
	}
};

splay_tree s[maxn];

int main() {
	buf -> ls = buf -> rs = buf;
	read(n); read(m);
	for (int i = 1; i <= n; i++) {
		read(a[i]);
		update(i, a[i]);
		for (int j = 1; j * j <= a[i]; j++) {
			if (a[i] % j == 0) {
				s[j].insert(i);
				s[a[i] / j].insert(i);
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		read(op); read(l); read(r);
		if (op & 1) {
			read(tmp);
			if (tmp ^ 1) s[tmp].work(l, r, tmp);
		}
		else write(ask(r) - ask(l - 1), '\n');
	}
	return 0;
}