## 【树状数组】query

### 传送门

l \le i < j \le r 而且 \min(p_i,p_j) = \gcd(p_i,p_j )

nlogn的时间里可以找出所有pair的对数，并以(l,r)的二元组表示。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
typedef pair<int,int> pii;
int pos[maxn], a[maxn];
vector<pii> v;
vector<pair<pii,int> > q;
int c[maxn];
int n, m;
{
for(; x <= n; x += x & -x) c[x] ++ ;
}
{
int res = 0;
for(; x; x -= x & -x) res += c[x];
return res;
}
int ans[maxn];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]), pos[a[i]] = i;
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j += i)
{
if(pos[i] < pos[j]) v.push_back({-pos[i], pos[j]});
else if(pos[i] > pos[j]) v.push_back({-pos[j],pos[i]});
}
}

for(int i = 1; i <= m; i++)
{
int l, r;
scanf("%d%d", &l, &r);
q.push_back({{-l, r}, i});
}
sort(q.begin(), q.end());
sort(v.begin(), v.end());
int i = 0, j = 0;
for(i = 0; i < q.size(); i++)
{
int L = -q[i].first.first, R = q[i].first.second;
while(j < v.size() && -v[j].first >= L)
}
for(i = 1; i <= m; i++) printf("%d\n", ans[i]);
}
/*
4 4
3 1 4 2
1 2
2 3
1 3
3 4
*/