题目链接：https://codeforces.com/gym/101991/problem/G
题意：给出 n 个数，q 次询问区间[ li，ri ]之间有多少个 GCD = di 的连续子区间。
题解：类似HDU 5726，可以先看一下这个blog：https://blog.****.net/u013569304/article/details/51987053
考虑离线，先预处理出[ 1，n ]之间所有的GCD，同时需要记录每种 GCD 的区间，方法是固定一个右端点R，对于区间[ L，R ]，假设 GCD（L，R）= D，可以找到使得GCD（L，R）突变的点 pos，即 x ∈ [ L，pos ] 都有 GCD（x，R） = D，然后利用线段树可以统计出 GCD = D 的区间个数。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset((a),(b),sizeof(a))
#define mp(a,b) make_pair(a,b)
#define pi acos(-1)
#define pii pair<int,int>
#define pb push_back
const int INF = 0x3f3f3f3f;
const double eps = 1e-;
const int maxn = 1e5 + ;
const int maxm = 1e6 + ;
const ll mod = 1e9 + ; int a[maxn]; struct node {
int l,r,id;
}; bool cmp(node x,node y) {
if(x.id != y.id) return x.id < y.id;
return x.l > y.l;
} vector<node>vec[maxm];
vector<pii>now,nex; ll sum[maxn<<],ans[maxn];
int lazy[maxn<<]; inline void init(int rt,int l,int r) {
if(!sum[rt] && !lazy[rt]) return ;
sum[rt] = lazy[rt] = ;
if(l == r) return ;
int mid = (l + r) >> ;
init(rt<<,l,mid);
init(rt<<|,mid + ,r);
} inline void pushdown(int rt,int l,int r) {
if(lazy[rt]) {
int mid = (l + r) >> ;
lazy[rt<<] += lazy[rt];
lazy[rt<<|] += lazy[rt];
sum[rt<<] += 1ll * (mid - l + ) * lazy[rt];
sum[rt<<|] += 1ll * (r - mid) * lazy[rt];
lazy[rt] = ;
}
} inline void update(int rt,int l,int r,int ql,int qr) {
if(ql <= l && qr >= r) {
lazy[rt]++;
sum[rt] += (ll)(r - l + );
return ;
}
pushdown(rt,l,r);
int mid = (l + r) >> ;
if(qr <= mid) update(rt<<,l,mid,ql,qr);
else if(ql > mid) update(rt<<|,mid + ,r,ql,qr);
else {
update(rt<<,l,mid,ql,mid);
update(rt<<|,mid + ,r,mid + ,qr);
}
sum[rt] = sum[rt<<] + sum[rt<<|];
} inline ll query(int rt,int l,int r,int ql,int qr) {
if(ql <= l && qr >= r) return sum[rt];
pushdown(rt,l,r);
int mid = (l + r) >> ;
if(qr <= mid) return query(rt<<,l,mid,ql,qr);
else if(ql > mid) return query(rt<<|,mid + ,r,ql,qr);
else return query(rt<<,l,mid,ql,mid) + query(rt<<|,mid + ,r,mid + ,qr);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#else
freopen("gcdrng.in", "r", stdin);
#endif
int t;
scanf("%d",&t);
while(t--) {
int n,q;
scanf("%d%d",&n,&q);
for(int i = ; i <= n; i++) scanf("%d",&a[i]);
for(int i = ; i <= q; i++) {
int l,r,d;
scanf("%d%d%d",&l,&r,&d);
vec[d].push_back({-i,l,r});
}
nex.clear();
for(int i = ; i <= n; i++) {
now.clear();
now.push_back(mp(a[i],));
for(int j = ; j < nex.size(); j++) {
pii p = nex[j];
int g = __gcd(now[now.size() - ].first,p.first);
if(g == now[now.size() - ].first) now[now.size() - ].second += p.second;
else now.push_back(mp(g,p.second));
}
int r = i;
for(int j = ; j < now.size(); j++) {
pii p = now[j];
vec[p.first].push_back({r - p.second + ,r,i});
r -= p.second;
}
nex = now;
}
for(int i = ; i <= 1e6; i++) {
init(,,n);
sort(vec[i].begin(),vec[i].end(),cmp);
for(int j = ; j < vec[i].size(); j++) {
node p = vec[i][j];
if(p.l > ) update(,,n,p.l,p.r);
else ans[-p.l] = query(,,n,p.r,p.id);
}
vec[i].clear();
}
for(int i = ; i <= q; i++) printf("%lld\n",ans[i]);
}
return ;
}