本文主要是介绍【Codeforces Round 271 (Div 2)F】【贪心 线段树】Ant colony 区间段内是其他所有数因子的数的个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1,class T2>inline void gmax(T1 &a,T2 b){if(b>a)a=b;}
template <class T1,class T2>inline void gmin(T1 &a,T2 b){if(b<a)a=b;}
const int N=0,M=0,Z=1e9+7,ms63=1061109567;
struct A
{int l,r;int gcd,minv,num;
}a[1<<18];
int n,m;
int l,r;
int GCD,MINV,NUM;
int gcd(int x,int y)
{return y==0?x:gcd(y,x%y);
}
void pushup(int o)
{a[o].gcd=gcd(a[ls].gcd,a[rs].gcd);a[o].minv=min(a[ls].minv,a[rs].minv);a[o].num=0;if(a[o].minv==a[ls].minv)a[o].num+=a[ls].num;if(a[o].minv==a[rs].minv)a[o].num+=a[rs].num;
}
void build(int o,int l,int r)
{a[o].l=l;a[o].r=r;if(a[o].l==a[o].r){scanf("%d",&a[o].gcd);a[o].minv=a[o].gcd;a[o].num=1;return;}int m=(l+r)>>1;build(ls,l,m);build(rs,m+1,r);pushup(o);
}
void get(int o,int l,int r)
{if(a[o].l==l&&a[o].r==r){if(GCD==-1)GCD=a[o].gcd;else GCD=gcd(GCD,a[o].gcd);if(a[o].minv<MINV){MINV=a[o].minv;NUM=a[o].num;}else if(a[o].minv==MINV){NUM+=a[o].num;}return;}int m=(a[o].l+a[o].r)>>1;if(r<=m)get(ls,l,r);else if(l>m)get(rs,l,r);else{get(ls,l,m);get(rs,m+1,r);}
}
int main()
{while(~scanf("%d",&n)){build(1,1,n);scanf("%d",&m);for(int i=1;i<=m;++i){scanf("%d%d",&l,&r);MINV=1e9;NUM=0;GCD=-1;get(1,l,r);if(GCD%MINV==0)printf("%d\n",r-l+1-NUM);else printf("%d\n",r-l+1);}}return 0;
}
/*
【trick&&吐槽】【题意】
给你一个长度为n（1e5）的数列。
每个数的数值都在[1,1e9]范围。
然后有m（1e5）个询问。
对于每个询问，问你区间为[l,r]内，有多少个数，是这个区间内其他所有数的因子【类型】
贪心 线段树【分析】
呀嘿嘿，这题被我秒掉了。很显然，有一个贪心结论，如果一个数，是区间内所有数的因子的话。
那么必要条件是，
1，这个数是这区间段最小的数
2，这个数是这区间段内所有数的因子，也就是说，这个数是这区间段所有数gcd的因子。于是，我们只要求出区间最小数和（同时也记录个数），区间gcd，然后就可以AC这道题啦。【时间复杂度&&优化】
O（mlogn）*/这篇关于【Codeforces Round 271 (Div 2)F】【贪心 线段树】Ant colony 区间段内是其他所有数因子的数的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
