Codeforces Round \ # 271 (Div. 2) F - Ant colony 선분 트 리 + GCD

Codeforces Round #271 (Div. 2) F - Ant colony
제목:
시퀀스 지정 M 질문 이 있어 요.
질문 할 때마다  주어진 구간 에 몇 개의 수가 있 습 니까?   구간 의 다른 수 를 제거 할 수 없다. 적어도 한 번 은..
생각:
제목 을 바 꾸 면 구간 에 몇 개의 수가 다른 수 를 정리 할 수 있 는 지 를 구 하 는 것 이다.
사실 이 숫자 는 구간 의 gcd 입 니 다.  그래서 우 리 는 구간 에서 이 수의 개 수 를 구하 기만 하면 된다.
후자  새로운 방법 을 배우다  기록 은 매번 위치 가 나타 날 때마다 2 분 씩 찾 습 니 다.

#include 
#define lson num<<1
#define rson num<<1|1
#define gl l,m,lson
#define gr m+1,r,rson
#define PARA int l=1,int r=n,int num=1
using namespace std;
const int MAXN = 1e5+100;
int n;
int gcd(int a,int b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}

int a[MAXN];
struct Node
{
    int st[MAXN<<2];
    void pushUp(int num)
    {
        st[num]=gcd(st[lson],st[rson]);
    }
    void init(PARA)
    {
        int m=l+r>>1;
        if(l!=r)
            init(gl),init(gr),pushUp(num);
        else
            st[num]=a[l];
    }
    int query(int a,int b,PARA)
    {
        if(a<=l&&r<=b)
            return st[num];
        else
        {
            int m=l+r>>1;
            if(b<=m)
                return query(a,b,gl);
            else if(a>m)
                return query(a,b,gr);
            else
                return gcd(query(a,b,gl),query(a,b,gr));
        }
    }
}soul;

struct myPair
{
    int a,b;
    void init(int _a,int _b)
    {
        a=_a;
        b=_b;
    }
    bool operator
inline void scan_d(T &ret) {
	char c; ret=0;
	while((c=getchar())'9');
	while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
}

int main()
{
    scan_d(n);
    for(int i=1;i<=n;i++)
        scan_d(a[i]),pr[i].init(a[i],i);
    sort(pr+1,pr+1+n);
    soul.init();

    int m,l,r,rl,rr,v;
    scan_d(m);
    while(m--)
    {
        scan_d(l);
        scan_d(r);
        v=soul.query(l,r);
        prt.init(v,l);
        rl=lower_bound(pr+1,pr+1+n,prt)-(pr+1);
        prt.init(v,r+1);
        rr=lower_bound(pr+1,pr+1+n,prt)-(pr+1);
        printf("%d
",r-l+1-(rr-rl));
    }
    return 0;
}