#6164. 「美团 CodeM 初赛 Round A」数列互质

内存限制:512 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给出一个长度为 n 的数列 { a_1 , a_2 , a_3 , ... , a_n } ,以及 m 组询问 ( l_i , r_i , k_i) ,求区间 [ l_i , r_i ] 中有多少数在该区间中的出现次数与 k_i 互质。

输入格式

第一行,两个正整数 n , m

第二行, n 个正整数 a_i 描述这个数列。

接下来 m 行,每行三个正整数 l_i , r_i , k_i ,描述一次询问。

输出格式

输出 m 行,即每次询问的答案。

样例

样例输入

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

数据范围与提示

  • 1\le n,m\le 5\times 10^4
  • 1\le a_i\le n
  • 1\le l_i\le r_i\le n
  • 1\le k_i\le n