「CF475D」CGCDSSQ
2014年10月6日4,5840
Given a sequence of integers a1, …, an and q queries x1, …, xq on it. For each query xi you have to count the number of pairs (l, r)such that 1 ≤ l ≤ r ≤ n and gcd(al, al + 1, …, ar) = xi.
is a greatest common divisor of v1, v2, …, vn, that is equal to a largest positive integer that divides all vi.
Input
The first line of the input contains integer n, (1 ≤ n ≤ 105), denoting the length of the sequence. The next line contains n space separated integers a1, …, an, (1 ≤ ai ≤ 109).
The third line of the input contains integer q, (1 ≤ q ≤ 3 × 105), denoting the number of queries. Then follows q lines, each contain an integer xi, (1 ≤ xi ≤ 109).
Output
For each query print the result in a separate line.
Sample test(s)
input
1 2 3 4 5 6 7 8 |
3 2 6 3 5 1 2 3 4 6 |
output
1 2 3 4 5 |
1 2 2 0 1 |
input
1 2 3 4 5 6 7 8 9 10 11 12 13 |
7 10 20 3 15 1000 60 16 10 1 2 3 4 5 6 10 20 60 1000 |
output
1 2 3 4 5 6 7 8 9 10 |
14 0 2 2 2 0 2 2 1 1 |
题解
由于gcd(a,b)=a或者<=a/2
那么枚举区间的左端点,随着右端点的推移动,区间gcd最多变化log次
那么只要通过二分找出这log个区间即可
至于区间gcd询问,可以考虑线段树或者st表,但这题线段树会多一个log是会被卡的T T
线段树(超时)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<map> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,q; int a[100005],x[300005]; map<int,ll> ans; struct data{int l,r,v;}t[400005]; int gcd(int x,int y) { return y==0?x:gcd(y,x%y); } void build(int k,int l,int r) { t[k].l=l;t[k].r=r; if(l==r){t[k].v=a[l];return;} int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); t[k].v=gcd(t[k<<1].v,t[k<<1|1].v); } int query(int k,int x,int y) { int l=t[k].l,r=t[k].r; if(x==l&&y==r)return t[k].v; int mid=(l+r)>>1; if(y<=mid)return query(k<<1,x,y); else if(x>mid)return query(k<<1|1,x,y); else return gcd(query(k<<1,x,mid),query(k<<1|1,mid+1,y)); } int find(int x,int l,int L) { int r=n,ans=0; while(l<=r) { int mid=(l+r)>>1; if(query(1,L,mid)!=x)r=mid-1; else ans=mid,l=mid+1; } return ans; } void solve(int x) { int t=a[x],now=x; while(1) { int last=now; now=find(t,now,x); if(ans[t])ans[t]+=now-last+1; if(now==n)return; now++;t=query(1,x,now); } } int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); build(1,1,n); q=read(); for(int i=1;i<=q;i++) x[i]=read(),ans[x[i]]=1; for(int i=1;i<=n;i++)solve(i); for(int i=1;i<=q;i++) printf("%I64d\n",ans[x[i]]-1); return 0; } |
ST表
注意不要调用系统的log,会很慢
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<map> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int bin[20],Log[100005]; int n,q; int a[100005],x[300005],f[100005][17]; map<int,ll> ans; struct data{int l,r,v;}t[400005]; int gcd(int x,int y) { return y==0?x:gcd(y,x%y); } void pre() { for(int i=1;i<=n;i++)f[i][0]=a[i]; for(int i=1;i<=16;i++) for(int x=1;x<=n;x++) if(x+bin[i]-1<=n) f[x][i]=gcd(f[x][i-1],f[x+bin[i-1]][i-1]); else break; } int query(int l,int r) { int t=Log[r-l+1]; return gcd(f[l][t],f[r-bin[t]+1][t]); } int find(int x,int l,int L) { int r=n,ans=0; while(l<=r) { int mid=(l+r)>>1; if(query(L,mid)!=x)r=mid-1; else ans=mid,l=mid+1; } return ans; } void solve(int x) { int t=a[x],now=x; while(1) { int last=now; now=find(t,now,x); if(ans[t])ans[t]+=now-last+1; if(now==n)return; now++;t=query(x,now); } } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; n=read(); Log[0]=-1;for(int i=1;i<=n;i++)Log[i]=Log[i>>1]+1; for(int i=1;i<=n;i++) a[i]=read(); pre(); q=read(); for(int i=1;i<=q;i++) x[i]=read(),ans[x[i]]=1; for(int i=1;i<=n;i++)solve(i); for(int i=1;i<=q;i++) printf("%I64d\n",ans[x[i]]-1); return 0; } |
Subscribe
分类目录
热门文章
- 7897「小奇模拟赛2」[BZOJ3784] 小奇的树
- 7789NOI2010 超级钢琴
- 65502017ACM萧山训练第5场(2016 Pacific Northwest - Division 1)
- 6369「POJ3693」Maximum repetition substring
- 4911「codechef」April Challenge 2015
- 4584「CF475D」CGCDSSQ
- 4296「BZOJ1699」[Usaco2007 Jan] Balanced Lineup排队
- 4278「NOIP模拟赛」数字对
- 39952016 ACM / ICPC Asia Regional Dalian Online
- 3695「BZOJ1636」[Usaco2007 Jan] Balanced Lineup
- 3648「vijos1514」天才的记忆
- 3574PKUSC 2014 #4
近期评论
- 匿名发表在《hzwer.com 博客导航》
- 匿名发表在《hzwer.com 博客导航》
- 匿名发表在《hzwer.com 博客导航》
- 匿名发表在《留言板》
- 匿名发表在《你好,世界》