2585. [河南省队2016]HH树

【题目描述】

有一个序列A，长为n，HH有m个询问，每次询问包含两个整数L，R。每次问你L到R内有多少对互质的数。

注意：(A[i],A[j])和(A[j],A[i])算作一对

【输入格式】

第一行两个整数n,m。 (n<=50000,m<=50000)

第二行n个整数表示序列A。 (1<=Ai<=50000)

接下来m行每行2个整数L，R。(1<=L<=R<=n)

【输出格式】

一共m行，每行一个整数表示第i个询问的答案。

【输入样例】

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

【输出样例】

1
3
5
9
1

【样例说明】

因为konicy传数据时挂掉了题面。于是自己改了改Mike的题面。。。。

从前Mike写了假的莫队被konicy造数据HACK了……

Mike：数据是Mike自己造的，有官测数据顶掉就好了。