1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
ll pre[N];
int a[N],vis[N],pos[N];
struct node
{
int l,r,id;
bool operator< (const node& nod)const
{
return l<nod.l;
}
}q[N];
ll sum[N],ans[N];
int lowbit(int x)
{
return x&(-x);
}
void add(int x)
{
for(int i=x;i<N;i+=lowbit(i))
sum[i]++;
}
int query(int x)
{
ll ans=0;
for(int i=x;i;i-=lowbit(i))
ans+=sum[i];
return ans;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
ll sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]),pos[a[i]]=i;
sum=sum+n/i-1;
}
pre[n]=sum;
for(int i=n;i>=2;i--)
{
pre[i-1]=pre[i];
for(int j=1;j<=sqrt(a[i]);j++)
{ if(a[i]==j)continue;
if(a[i]%j==0)
{
if(!vis[j])
pre[i-1]--;
if(a[i]/j!=j&&j!=1&&!vis[a[i]/j])
pre[i-1]--;
}
}
for(int j=2;j*a[i]<=n;j++)
{
if(!vis[a[i]*j])
pre[i-1]--;
}
vis[a[i]]=1;
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)
scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
sort(q+1,q+1+m);
int p=1;
for(int i=1;i<=m;i++)
{
while(p<q[i].l)
{
for(int j=1;j<=sqrt(a[p]);j++)
{
if(a[p]%j==0)
{
if(!vis[j])
add(pos[j]);
if(a[p]/j!=j&&j!=1&&!vis[a[p]/j])
add(pos[a[p]/j]);
}
}
for(int j=2;j*a[p]<=n;j++)
{
if(!vis[a[p]*j])
add(pos[a[p]*j]);
}
vis[a[p]]=1;
p++;
}
ans[q[i].id]=pre[q[i].r]-pre[q[i].l-1]-query(q[i].r)+query(q[i].l-1);
}
for(int i=1;i<=m;i++)
printf("%lld\n",ans[i]);
return 0;
}
|