2015年3月16日 星期一

Codechef January Challenge 2015 Gcd Queries

// http://www.codechef.com/problems/GCDQ
#include <iostream>
#include <cstdio>

using namespace std;

int T;
int N, Q;
int A[200000];

int gcd(int a, int b)
{
    while( a && b )
    {
        if( a < b ) swap(a, b);
        a %= b;
    }

    return a+b;
}

struct Node
{
    Node *l, *r;
    int num;

    Node(){ l = r = NULL; num = 0; }
};

Node mem[400000]; int clk;

void pull(Node *O, int L, int R)
{
    if( L+1 == R )
    {
        O->num = A[L];
    }
    else
    {
        O->num = gcd(O->l->num, O->r->num);
    }
}

void build(Node *&O, int L, int R)
{
    O = &mem[clk++];

    if( L+1 == R )
    {
        pull(O, L, R);
        return;
    }

    build(O->l, L, (L+R)/2);
    build(O->r, (L+R)/2, R);

    pull(O, L, R);
}

void destroy(Node *&O, int L, int R)
{
    if( L+1 != R )
    {
        destroy(O->l, L, (L+R)/2);
        destroy(O->r, (L+R)/2, R);
    }

    delete O;
}

int ask(Node *O, int L, int R, int A, int B)
{
    if( B <= L || R <= A ) return 0;
    else if( A <= L && R <= B ) return O->num;
    else
    {
        int v1 = ask(O->l, L, (L+R)/2, A, B);
        int v2 = ask(O->r, (L+R)/2, R, A, B);

        return gcd(v1, v2);
    }
}

Node *root;

int main()
{
    scanf("%d", &T);

    while( T-- )
    {
        scanf("%d %d", &N, &Q);

        for(int Ni = 1; Ni <= N; Ni++)
            scanf("%d", &A[Ni]);

        clk = 0;
        build(root, 1, N+1);

        for(int Qi = 0; Qi < Q; Qi++)
        {
            int L, R;
            scanf("%d %d", &L, &R);

            int v1 = ask(root, 1, N+1, 1, L);
            int v2 = ask(root, 1, N+1, R+1, N+1);

            printf("%d\n", gcd(v1,v2));
        }
    }
}

沒有留言:

張貼留言