问题4355--这不珂学

4355: 这不珂学

[命题人 : ]
时间限制 : 6.000 sec  内存限制 : 128 MB

提交

题目描述

给出 n 个正整数，有 Q 次询问，每次询问给出一对区间[l, r]，求这个区间内互质的对数。

输入

多组测试。每组输入形如：
n Q
a1 a2 a3 .... an
l1 r1
l2 r2
...
lQ rQ
 
1<= ai <= 10000, 1<=n<=20000, 1<=Q<=100000, 1<=li<=ri<=n
 

输出

每组输出形如：
ans(1)
ans(2)
...
ans(Q)
 

样例输入 Copy 

5 4
1 2 3 4 5
1 2
2 3
3 5
2 2

样例输出 Copy 

1
1
3
0

来源/分类

lyf 
提交