题目链接：http://acm.fzu.edu.cn/problem.php?pid=2224
//#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 1e6 + ;
int a[N/ + ], bit[N]; //_pos存的是gcd上一次出现的位置
vector <P> ans[N/ + ]; //存的是以i为右端点的gcd
map <int, int> _pos;
struct query {
int l, r, pos;
bool operator <(const query& cmp) const {
return r < cmp.r;
}
}q[N/ + ];
int res[N/ + ]; //答案 void init(int n) {
_pos.clear();
memset(bit, , sizeof(bit));
for(int i = ; i <= n; ++i) {
ans[i].clear();
}
} int GCD(int a, int b) {
return b ? GCD(b, a % b): a;
} void add(int i, int x) {
for( ; i <= N; i += (i&-i))
bit[i] += x;
} int sum(int i) {
int s = ;
for( ; i >= ; i -= (i&-i))
s += bit[i];
return s;
} int main()
{
int n, m, t;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
init(n);
for(int i = ; i <= n; ++i) {
scanf("%d", a + i);
}
for(int i = ; i <= m; ++i) {
scanf("%d %d", &q[i].l, &q[i].r);
q[i].pos = i;
}
for(int i = ; i <= n; ++i) {
int x = a[i], y = i;
for(int j = ; j < ans[i - ].size(); ++j) {
int gcd = GCD(x, ans[i - ][j].first);
if(gcd != x) {
ans[i].push_back(make_pair(x, y));
x = gcd, y = ans[i - ][j].second;
}
}
ans[i].push_back(make_pair(x, y));
}
sort(q + , q + m + );
int p = ;
for(int i = ; i <= n; ++i) {
for(int j = ; j < ans[i].size(); ++j) {
if(!_pos[ans[i][j].first]) {
add(ans[i][j].second, );
_pos[ans[i][j].first] = ans[i][j].second;
} else {
add(_pos[ans[i][j].first], -);
_pos[ans[i][j].first] = ans[i][j].second;
add(ans[i][j].second, );
}
}
while(i == q[p].r && p <= m) {
res[q[p].pos] = sum(q[p].r) - sum(q[p].l - );
++p;
}
}
for(int i = ; i <= m; ++i) {
printf("%d\n", res[i]);
}
}
return ;
}