HDU 5869 Different GCD Subarray Query

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

询问一个区间里不同的gcd有几种，先算出以每个点为结尾的不同gcd的值，并且可以知道对应的范围

这样就相当于求一个区间里不同的数有一个，用树状数组即可。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,int>
#define in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-8;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int T, n,m, x[N],l,r;
int ft[N],nt[N],u[N],v[N],sz;
int f[N],ans[N];
int pre[N*5];

int gcd(int x,int y)
{
    return x%y?gcd(y,x%y):y;
}

void add(int x,int y)
{
    for (int i=x;i<=n;i+=low(i)) f[i]+=y;
}

int sum(int x)
{
    int res=0;
    for (int i=x;i;i-=low(i)) res+=f[i];
    return res;
}

int main()
{
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        int g=0;
        rep(i,1,n) scanf("%d",&x[i]),g=max(g,x[i]);
        rep(i,1,n) ft[i]=-1,f[i]=sz=0;
        rep(i,1,g) pre[i]=0;
        rep(i,1,m)
        {
            scanf("%d%d",&l,&r);
            u[sz]=l; v[sz]=i; nt[sz]=ft[r]; ft[r]=sz++;
        }
        stack<pii> a, b;
        rep(i, 1, n)
        {
            a.push(mp(x[i], 1));
            while (!a.empty()) b.push(mp(gcd(a.top().ff, x[i]), a.top().ss)), a.pop();
            while (!b.empty())
            {
                pii q = b.top();    b.pop();
                if (!a.empty() && a.top().ff == q.ff) q.ss += a.top().ss, a.pop();
                a.push(q);
            }
            while (!a.empty()) b.push(a.top()), a.pop();
            int bef = 0;
            while (!b.empty())
            {
                add(pre[b.top().ff]+1,1);
                bef += b.top().ss;
                add(bef+1,-1);
                pre[b.top().ff]=bef;
                a.push(b.top()), b.pop();
            }
            loop(j,ft[i],nt) ans[v[j]]=sum(u[j]);
        }    
        rep(i,1,m) printf("%d\n",ans[i]);
    }
    return 0;
}