题目链接
http://acm.split.hdu.edu.cn/showproblem.php?pid=5869
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 Source 2016 ACM/ICPC Asia Regional Dalian Online Recommend wange2014 | We have carefully selected several similar problems for you: 5877 5876 5874 5873 5872 题意：输入N和Q，表示有N个数的一个序列，Q次询问，每次输入 l 和 r 表示一个区间，求这个区间不同的最大公倍数的个数（由这个区间的子区间得到）； 思路：对数列进行GCD离散处理（~我也是才知道还有这样的离散~） for(int i=1;i<=N;i++) { int tot=a[i],pos=i; for(int j=0;j<v[i-1].size();j++) { int r=__gcd(a[i],v[i-1][j].first); if(tot!=r) { v[i].push_back(make_pair(tot,pos)); tot=r; pos=v[i-1][j].second; } } v[i].push_back(make_pair(tot,pos)); } 然后对Q次询问离线处理，先输入Q次询问的区间，然后按右端点从小到大排序，i从1~N循环，当i==node[len].r 则 ans[node[len].id]=Sum(i)-Sum(node[len].l-1) ; 可以方便快速的用树状数组处理； 代码如下： #include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> #include <map> #include <vector> using namespace std; int a[100005]; int c[1000005]; int vis[1000005]; int sum[100005]; struct Node { int l,r; int id; }node[100005]; bool cmp(const Node s1,const Node s2) { return s1.r<s2.r; } vector<pair<int,int> > v[100005]; int __gcd(int x,int y) { int r=x%y; x=y; y=r; if(r==0) return x; return __gcd(x,y); } int Lowbit(int t) { return t&(t^(t-1)); } int Sum(int x) { int sum = 0; while(x > 0) { sum += c[x]; x -= Lowbit(x); } return sum; } void add(int li,int t) { while(li<=1000005) { c[li]+=t; li=li+Lowbit(li); } } int main() { int N,Q; while(scanf("%d%d",&N,&Q)!=EOF) { for(int i=1;i<=N;i++) scanf("%d",&a[i]); for(int i=1;i<=N;i++) { int tot=a[i],pos=i; for(int j=0;j<v[i-1].size();j++) { int r=__gcd(a[i],v[i-1][j].first); if(tot!=r) { v[i].push_back(make_pair(tot,pos)); tot=r; pos=v[i-1][j].second; } } v[i].push_back(make_pair(tot,pos)); } for(int i=0;i<Q;i++) scanf("%d%d",&node[i].l,&node[i].r),node[i].id=i; sort(node,node+Q,cmp); memset(c,0,sizeof(c)); memset(vis,0,sizeof(vis)); int len=0; for(int i=1;i<=N;i++) { for(int j=0;j<v[i].size();j++) { int s1=v[i][j].first; int s2=v[i][j].second; if(vis[s1]){ add(vis[s1],-1); } vis[s1]=s2; add(s2,1); } while(node[len].r==i) { sum[node[len].id]=Sum(i)-Sum(node[len].l-1); len++; } } for(int i=0;i<Q;i++) printf("%d\n",sum[i]); for(int i=0;i<=N;i++) v[i].clear(); } return 0; }
转载于:https://www.cnblogs.com/chen9510/p/5867587.html
相关资源：各显卡算力对照表！