数列互质
题目描述
给出一个长度为 n 的数列 { a[1] , a[2] , a[3] , … , a[n] }，以及 m 组询问 ( l[i] , r[i] , k[i])。 求数列下标区间在 [ l[i] , r[i] ] 中有多少数在该区间中的出现次数与 k[i] 互质（最大公约数为1）。
输入描述: 第一行，两个正整数 n , m (1 ≤ n, m ≤ 50000)。 第二行，n 个正整数 a[i] (1 ≤ a[i] ≤ n)描述这个数列。 接下来 m 行，每行三个正整数 l[i] , r[i] , k[i] (1 ≤ l[i] ≤ r[i] ≤ n, 1 ≤ k[i] ≤ n)，描述一次询问。 输出描述: 输出 m 行，即每次询问的答案。 示例1 输入 复制
10 5
1 1 1 1 1 2 2 2 2 2
4 7 2
4 7 3
4 8 2
4 8 3
3 8 3
输出 复制
0
2
1
1
0
题解：
莫队算法，就裸题的基础上进行修改，题目问的多少数在该区间中的出现次数与k[i]互质，我们用莫队来维护区间内每个数出现的次数，然后我们枚举区间内出现的数的次数是否与k[i]互质，枚举的话不要从1~n全部枚举，因为题目可能只给了一部分数，其他在重复，所以我们可以用set来存数，因为set有自动筛重的功能 大体如上，还是比较简单偏模板的题，具体可见代码
代码：
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
ll
gcd(ll a
,ll b
)
{
if(b
==0)return a
;
else return gcd(b
,a
%b
);
}
const ll maxn
=1e6+9;
ll n
,m
;
ll a
[maxn
],pos
[maxn
],num
[maxn
],ans
[maxn
];
struct node
{
ll l
,r
,k
,id
;
}t
[maxn
];
bool cmp(node a
,node b
)
{
if(pos
[a
.l
]==pos
[b
.l
])return a
.r
<b
.r
;
else return pos
[a
.l
]<pos
[b
.l
];
}
int L
=1,R
=0;
void del(int x
)
{
num
[x
]--;
}
void add(int x
)
{
num
[x
]++;
}
void solve(node w
)
{
while(w
.l
>L
){del(a
[L
++]);}
while(w
.r
>R
){add(a
[++R
]);}
while(w
.l
<L
){add(a
[--L
]);}
while(w
.r
<R
){del(a
[R
--]);}
}
set
<ll
>s
;
int main()
{
cin
>>n
>>m
;
for(int i
=1;i
<=n
;i
++)
{
cin
>>a
[i
];
s
.insert(a
[i
]);
}
ll block
=sqrt(n
);
for(int i
=1;i
<=m
;i
++)
{
cin
>>t
[i
].l
>>t
[i
].r
>>t
[i
].k
;
t
[i
].id
=i
;
pos
[i
]=i
/block
;
}
sort(t
+1,t
+1+m
,cmp
);
for(int i
=1;i
<=m
;i
++)
{
solve(t
[i
]);
int tot
=0;
for(set
<ll
>::iterator it
=s
.begin();it
!=s
.end();it
++)
{
if(gcd(num
[*it
],t
[i
].k
)==1&&num
[*it
])tot
++;
}
ans
[t
[i
].id
]=tot
;
}
for(int i
=1;i
<=m
;i
++)
{
cout
<<ans
[i
]<<endl
;
}
}
