这个map我也是醉了。
这个 主要是 那个 不同gcd值得区间数预处理难弄。
a[1...i]=a[1...i-1]+a[i...i]; 当前区间:不同的gcd值相对应的区间数=之前区间:不同的gcd值相对应的区间数+gcd(num[i],之前区间的某个gcd);
#include"iostream" #include"vector" #include"set" #include"queue" #include"algorithm" #include"map" #include"cstdio" #include"cstring" #include"string" #define sf scanf #define pf printf #define INF 100000000000000 #define eps 1e-6 #define FP freopen("a.txt","r",stdin); using namespace std; typedef long long ll; const int maxn=100010; int a[maxn*4]; int b[maxn]; map<int,ll>ans,m1,m2; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } void up(int rt) { a[rt]=gcd(a[rt<<1],a[rt<<1|1]); } void build(int L,int R,int rt) { if(L==R) { a[rt]=b[L]; return ; } int Mid((L+R)/2); build(L,Mid,rt<<1); build(Mid+1,R,rt<<1|1); up(rt); } int query(int l,int r,int L,int R,int rt) { if(l==L&&R==r) return a[rt]; int Mid=(L+R)/2; int res; if(r<=Mid) return query(l,r,L,Mid,rt<<1); //必定在左子树 else if(l>Mid) return query(l,r,Mid+1,R,rt<<1|1);//必定在右子树 else return gcd(query(l,Mid,L,Mid,rt<<1),query(Mid+1,r,Mid+1,R,rt<<1|1)); } int main() { //FP int Case=1; int T; sf("%d",&T); while(T--) { m1.clear(); m2.clear(); ans.clear(); int n; sf("%d",&n); for(int i=1;i<=n;i++) sf("%d",b+i); build(1,n,1); //map<int,ll>::iterator it; //for(int i=1;i<=n;i++) // { // ans[b[i]]++; // m2[b[i]]++; // for(it=m1.begin();it!=m1.end();it++) // { // ll k=gcd(b[i],it->first); // ans[k]+=it->second; // m2[k]+=it->second; // } // m1.clear(); // for(it=m2.begin();it!=m2.end();it++) // m1[it->first]=it->second; // m2.clear(); // } map<int,ll>::iterator p; for(int i=1;i<=n;i++) // ans记录的是从1-n 中不同gcd的区间数 { //m2存储的是当前状态下不同gcd的区间数 然后复制给m1，那么下一次的时候m1存放的就是i-1的状态 ans[b[i]]++; m2[b[i]]++; for(p=m1.begin();p!=m1.end();p++) { int k=gcd(p->first,b[i]); ans[k]+=p->second; m2[k]+=p->second; } /*cout<<"i="<<i<<endl; cout<<"ans:"<<endl; for(p=ans.begin();p!=ans.end();p++) cout<<"gcd="<<p->first<<"的区间数:"<<p->second<<endl; cout<<"m1:"<<endl; for(p=m1.begin();p!=m1.end();p++) cout<<"gcd="<<p->first<<"的区间数:"<<p->second<<endl; cout<<"m2:"<<endl; for(p=m2.begin();p!=m2.end();p++) cout<<"gcd="<<p->first<<"的区间数:"<<p->second<<endl<<endl;*/ m1.clear(); m1=m2; m2.clear(); } printf("Case #%d:\n",Case++); int Q; sf("%d",&Q); for(int i=0;i<Q;i++) { int L,R; sf("%d%d",&L,&R); int num=query(L,R,1,n,1); pf("%d %I64d\n",num,ans[num]); } } return 0; }