区间互质

成绩 100 开启时间 2020年06月18日 星期四 11:05
折扣 0.8 折扣时间 2020年06月18日 星期四 11:05
允许迟交 是 关闭时间 2020年06月18日 星期四 11:05
输入文件 coprime.in 输出文件 coprime.out

【题目描述】区间互质（coprime）HDU 4777

给定n个数的序列，m个询问，询问区间[L，R]内，有多少个数与区间内其他所有的数都互质。

【输入格式】

输入包含多组数据，每组数据第一行为两个整数n和m，接下来一行有n个整数a[i]，随后m行询问，包含两个整数L和R　(1≤n，m，a[i]≤200 000，1≤L≤R≤n)。　

输入结束为两个0。

【输出格式】

对于每个询问，输出互质的数的个数。

【输入样例】

3 2

2 1 4

1 2

1 3

6 4

3 6 1 2 5 3

1 3

4 6

4 4

2 6

0 0

【输出样例】

2

1

1

3

1

2

【样例说明】

在第二组测试数据里，询问区间[2，6]的结果是2，因为只有1和5与其他所有数互质。