Problem Description
This is a simple problem. The teacher gives Bob a list of problems about GCD (Greatest Common Divisor). After studying some of them, Bob thinks that GCD is so interesting. One day, he comes up with a new problem about GCD. Easy as it looks, Bob cannot figure it out himself. Now he turns to you for help, and here is the problem:
Given an array a of N positive integers a1,a2,⋯aN−1,aN; a subarray of a is defined as a continuous interval between a1 and aN. In other words, ai,ai+1,⋯,aj−1,aj is a subarray of a, for 1≤i≤j≤N. For a query in the form (L,R), tell the number of different GCDs contributed by all subarrays of the interval [L,R].
Input
There are several tests, process till the end of input.
For each test, the first line consists of two integers N and Q, denoting the length of the array and the number of queries, respectively. N positive integers are listed in the second line, followed by Q lines each containing two integers L,R for a query.
You can assume that
1≤N,Q≤100000
1≤ai≤1000000
Output
For each query, output the answer in one line.
Sample Input
5 3
1 3 4 6 9
3 5
2 5
1 5
Sample Output
6
6
6
/** @Date : 2016-11-13-16.10
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version :
*/
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stack>
#include <queue>
#define pii pair<int , int>
#define FF first
#define SS second
#define MP(x,y) make_pair((x), (y))
#define LL long long
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5+2000;
int n,q;
int c[N];
int a[N];
int ans[N];
vector< pair<int,int> >gp[N];
int vis[1000010];
struct yuu
{
int l, r;
int m;
}Q[N];
int cmp(yuu a, yuu b)
{
return a.r < b.r;
}
int gcd(int a, int b)
{
return b?gcd(b, a % b):a;
}
void add(int x, int y)
{
while(x < N)
{
c[x] += y;
x += x & (-x);
}
}
int sum(int x)
{
int ans = 0;
while(x)
{
ans += c[x];
x -= x & (-x);
}
return ans;
}
void init()
{
MMF(c);
MMF(vis);
MMF(ans);
for(int i = 1; i <= n; i++)
{
int x = a[i];
int p = i;
for(int j = 0; j < gp[i-1].size(); j++)
{
int g = gcd(gp[i-1][j].FF, x);
if(x != g)
{
gp[i].push_back(MP(x, p));
x = g;
p = gp[i-1][j].SS;
}
}
gp[i].push_back(MP(x, p));
}
}
int main()
{
while(~scanf("%d%d", &n, &q))
{
MMF(a);
for(int i = 1; i <= n; i++ )
{
scanf("%d", a + i);
gp[i].clear();
}
init();
for(int i = 0; i < q; i++)
{
scanf("%d%d", &Q[i].l, &Q[i].r);
Q[i].m = i;
}
sort(Q, Q + q, cmp);
//////
int pos = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 0; j < gp[i].size(); j++)//
{
if(vis[gp[i][j].FF])
add(vis[gp[i][j].FF], -1);
vis[gp[i][j].FF] = gp[i][j].SS;
add(gp[i][j].SS, 1);
}
while(Q[pos].r == i)
{
ans[Q[pos].m] = sum(Q[pos].r) - sum(Q[pos].l-1);
pos++;
}
}
for(int i = 0; i < q; i++)
printf("%d ", ans[i]);
}
return 0;
}