首页 > 代码库 > HDU 5869 Different GCD Subarray Query 离线+树状数组

HDU 5869 Different GCD Subarray Query 离线+树状数组

2024-08-13 03:21:57   219人阅读

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 31 3 4 6 93 52 51 5
 

 

Sample Output
 
666
 

题意：

　　长度n的序列, m个询问区间[L, R], 问区间内的所有子段的不同GCD值有多少种.

题解：

　　固定右端点

　　预处理出 每个点向左延伸 的 不同gcd值

　　这样的 值不会超过log a 个

　　然后问题就变成了 问你一段区间内不同 gcd 值有多少，值是很少的 （询问一个区间有多少颜色的题型）

　　树状数组维护就可以了

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<vector>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18;const double Pi = acos(-1.0);const int N = 1e6+10, M = 1e2+11, mod = 1e9+7, inf = 2e9;int n,q,a[N],ans[N];int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b);}vector<pii> G[N];struct QQ{        int l,r,id;        bool operator < (const QQ &a) const {             return a.r > r;        }}Q[N];int C[N],vis[N];void update(int x,int c) {        for(int i =x; i < N; i+=i&(-i)) C[i] += c;}int ask(int x) {        int s =0 ;        for(int i = x; i; i-= i & (-i))s += C[i];        return s;}int main() {        while(scanf("%d%d",&n,&q)!=EOF) {            for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);            for(int i = 0; i <= n; ++i) G[i].clear();            for(int i = 1; i <= n; ++i) {                    int x = a[i];                    int y = i;                    for(int j = 0; j < G[i-1].size(); ++j) {                        int res = gcd(x,G[i-1][j].first);                        if(x != res) {                                G[i].push_back(MP(x,y));                                x = res;                                y = G[i-1][j].second;                        }                    }                    G[i].push_back(MP(x,y));            }            memset(C,0,sizeof(C));            memset(vis,0,sizeof(vis));            for(int i = 1; i <= q; ++i) {scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id = i;}            sort(Q+1,Q+q+1);            for(int R = 0, i = 1; i <= q; ++i) {                    while(R < Q[i].r) {                        R++;                        for(int j = 0; j < G[R].size(); ++j) {                            int res = G[R][j].first;                            int ids = G[R][j].second;                            if(vis[res]) update(vis[res],-1);                            vis[res] = ids;                            update(vis[res],1);                        }                    }                    ans[Q[i].id] = ask(R) - ask(Q[i].l-1);            }            for(int i = 1; i <= q; ++i) cout<<ans[i]<<endl;        }        return 0;}

 

HDU 5869 Different GCD Subarray Query 离线+树状数组


联系
我们