#include <iostream> #include <algorithm> using namespace std; const int N = (1<<17) + 1, K = 131071; int g[N<<1], Ans[N], Sum[N<<1], Lz[N<<1]; int getLeft(int cr){ cr += K; if (g[cr] == 1) return cr - K; int gcd = g[cr]; while (1){ if (cr & 1){ int gg = __gcd(gcd, g[cr - 1]); if (gg == 1){ cr--; break; } gcd = gg; } cr >>= 1; } while (cr <= K){ int gg = __gcd(gcd, g[cr*2+1]); cr <<= 1; if (gg == 1) cr++; else gcd = gg; } return cr - K; } int getRight(int cr){ cr += K; if (g[cr] == 1) return cr - K; int gcd = g[cr]; while (1){ if ((cr & 1) == 0){ int gg = __gcd(gcd, g[cr + 1]); if (gg == 1){ cr++; break; } gcd = gg; } cr >>= 1; } while (cr <= K){ int gg = __gcd(gcd, g[cr*2]); cr <<= 1; if (gg > 1) cr++, gcd = gg; } return cr - K; } void Upd(int cur, int vl, int sz){ Sum[cur] += vl * sz; Lz[cur] += vl; } void Push(int cur, int lc, int rc, int sz){ Upd(lc, Lz[cur], sz); Upd(rc, Lz[cur], sz); Lz[cur] = 0; } void Add(int l, int r, int v, int cur = 1, int st = 1, int en = N){ if (l >= en or r <= st) return; if (l <= st and r >= en){ Upd(cur, v, en - st); return; } int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2; Push(cur, lc, rc, mid - st); Add(l, r, v, lc, st, mid); Add(l, r, v, rc, mid, en); Sum[cur] = Sum[lc] + Sum[rc]; } int get(int l, int r, int cur = 1, int st = 1, int en = N){ if (l >= en or r <= st) return 0; if (l <= st and r >= en) return Sum[cur]; int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2; Push(cur, lc, rc, mid - st); return get(l, r, lc, st, mid) + get(l, r, rc, mid, en); } int main(){ for (int i=1;i<N;i++) Ans[i] = Ans[i-1] + i; int n, q; cin>>n>>q; g[K + 1] = g[K + n + 2] = 1; for (int i=2;i<=n+1;i++) cin>>g[i + K]; for (int i=K;i>=1;i--) g[i] = __gcd(g[i*2], g[i * 2 + 1]); for (int i=2;i<=n+1;i++){ int k = getLeft(i); Add(i, i + 1, i - k); } for (int i=1;i<=q;i++){ int t, l, r; cin>>t>>l>>r, l++; if (t == 2){ r++; int R = getRight(l); if (R > r) cout<<Ans[r - l + 1]<<'\n'; else cout<<Ans[R - l] + get(R, r + 1)<<'\n'; continue; } int cur = l; while (cur <= n + 1){ int L = getLeft(cur); int R = getRight(L + 1); if (L >= l) break; Add(cur, R, L - l); cur = R; } cur = l + K, g[cur] = r; while (cur > 1) cur >>= 1, g[cur] = __gcd(g[cur * 2], g[cur * 2 + 1]); cur = l; while (cur <= n + 1){ int L = getLeft(cur); int R = getRight(L + 1); if (L >= l) break; Add(cur, R, l - L); cur = R; } } }