2013年11月1日 星期五

STEP5 0132 汁男區間

[線段樹]

原本可以10分鐘寫完的QAQ 竟然卡__gcd



#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
using namespace std;
#define N 100000
int a[N];
int gcdTree[4*N];
int base;
int n;
int gcd(int a,int b)
{
    if(a*b==0)
        return a+b;
    if(b>a)
        a^=b^=a^=b;
    if(a%b==0)
        return b;
    return gcd(b,a%b);
}
void BuildTree()
{
    base=(int)pow(2,ceil(log2(n)))-1;
    if(base==(n-1))
        base=base*2+1;
    for(int lx=0;lx<n;lx++)
        gcdTree[lx+base+1]=a[lx];
    for(int lx=base;lx;lx--)
        gcdTree[lx]=gcd(gcdTree[lx*2],gcdTree[lx*2+1]);
}
int Ask(int a,int b)
{
    int re=0;
    for(a+=base-1,b+=base+1;a^b^1;a>>=1,b>>=1)
    {
        if(~a&1) re=gcd(re,gcdTree[a^1]);
        if(b&1) re=gcd(re,gcdTree[b^1]);
    }
    return re;
}
int main()
{
    int q;
    scanf("%d %d",&n,&q);
    for(int lx=0;lx<n;lx++)
        scanf("%d",&a[lx]);
    BuildTree();
    int a,b;
    while(q--)
    {
        scanf("%d %d",&a,&b);
        printf("%d\n",Ask(a,b));
    }
    return 0;
}

沒有留言:

張貼留言