提示: 欢迎访问OurACM平台。
Problem 2224 An exciting GCD problem

Accept: 52    Submit: 146
Time Limit: 5000 mSec    Memory Limit : 32768 KB

Problem Description

GG学长是个喜欢研究数论的boy,他现在有一个数组A,某天他突发奇想,

定义了:rgcd(l, r) = gcd(A[l], A[l + 1], ... , A[r - 1], A[r]),即为区间[L,R]中的所有数字的最大公约数

然后他对你进行了若干次询问,每次询问一个区间[l, r],让你求出这个区间内不同的rgcd(i, j) (l <= i <= j <= r)个数

Input

第一行输入T,表示有T组样例(T <= 20)

每组样例第一行为n,m,表示数组长度和询问次数(1 <= n <= 10000, 1<= m <= 100000)

接下来n个数字a1, a2, ... , an (1 <= ai <= 10^9)

接下来m个询问,每个询问一行l, r (1 <= l <= r <= n)

Output

每组样例输出m行,表示m次询问的答案

Sample Input

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

Sample Output

3 4

Source

FOJ有奖月赛-2016年4月(校赛热身赛)

Submit  Back  Status  Discuss