思路：参照脑补出的一个\(map\)套\(vector\)的写法，写起来比线段树短，运行时间比线段树快。

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
    
     using namespace std;#define fi first#define se second#define LL long long#define pb emplace_back#define pii pair
     
      const int N = 1e5 + 5;int T, n, q, a[N], L[N], R[N], d[N], cnt;LL ans[N];vector
      
        vc[N], p[N*20];vector
       
         sum[N*20];map
        
          mp, _p, mmp;int main() {    scanf("%d", &T);    for(int cs = 1; cs <= T; ++cs) {        scanf("%d", &n);        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);        scanf("%d", &q);        for (int i = 1; i <= q; ++i) {            scanf("%d %d", &L[i], &R[i]);            vc[R[i]].pb(i);        }        cnt = 0;        for (int i = 1; i <= n; ++i) {            for (auto it : mp) {                int g = __gcd(it.fi, a[i]);                if(_p.find(g) == _p.end()) _p[g] = it.se;            }            if(_p.find(a[i]) == _p.end()) _p[a[i]] = i;            mp = _p;            _p.clear();            vector
         
           tmp; for (auto it : mp) tmp.pb(it.se, it.fi); for (int j = 0; j < tmp.size(); ++j) { if(j+1 == tmp.size()) tmp[j].fi = i; else tmp[j].fi = tmp[j+1].fi-1; int now; if(mmp.find(tmp[j].se) == mmp.end()) { mmp[tmp[j].se] = ++cnt; now = cnt; } else now = mmp[tmp[j].se]; p[now].pb(tmp[j].fi); sum[now].pb(sum[now].size()==0?tmp[j].fi:sum[now].back()+tmp[j].fi); } for (int x : vc[i]) { int l = L[x]; int t = lower_bound(tmp.begin(), tmp.end(), pii{l, 0})-tmp.begin(); d[x] = tmp[t].se; int pp = mmp[d[x]]; t = lower_bound(p[pp].begin(), p[pp].end(), l)-p[pp].begin(); if(t-1>=0) ans[x] = sum[pp].back()-sum[pp][t-1]-(sum[pp].size()-t)*1LL*(l-1); else ans[x] = sum[pp].back()-sum[pp].size()*1LL*(l-1); } } printf("Case #%d:\n", cs); for (int i = 1; i <= q; ++i) printf("%d %lld\n", d[i], ans[i]); for (auto it : mmp) p[it.se].clear(), sum[it.se].clear(); mmp.clear(); mp.clear(); for (int i = 1; i <= n; ++i) vc[i].clear(); } return 0;}