Problem Description

The shorter, the simpler. With this problem, you should be convinced of this truth.

  

  You are given an array A of N postive
integers, and M queries
in the form (l,r).
A function F(l,r) (1≤l≤r≤N) is
defined as:

F(l,r)={AlF(l,r−1) modArl=r;l<r.

You job is to calculate F(l,r),
for each query (l,r).

 

Input

There are multiple test cases.

  

  The first line of input contains a integer T,
indicating number of test cases, and T test
cases follow. 

  

  For each test case, the first line contains an integer N(1≤N≤100000).

  The second line contains N space-separated
positive integers: A1,…,AN (0≤Ai≤109).

  The third line contains an integer M denoting
the number of queries. 

  The following M lines
each contain two integers l,r (1≤l≤r≤N),
representing a query.

 

Output

For each query(l,r),
output F(l,r) on
one line.

 

Sample Input

1

3

2 3 3

1

1 3

 

Sample Output

2


函数的意思解读出来就是在l到r的区间里，a[l],对区间里的数，逐个取余
那么比a[l]大的数，取余不变，主要看比a[l]小的数，所以在区间里找第一个比a[l]小的数，
然后继续在剩下的区间里面找比取完余的a[l]小的数

#include <iostream>

#include <string.h>

#include <stdio.h>

#include <algorithm>

#include <math.h>

#include <string>

#include <stdlib.h>

#include <vector>

using namespace std;

const int maxn=1e5;

int cmin[maxn*4+5];

int a[maxn+5];

int n,m;

int l,r;

int x;

void PushUp(int node)

{

    cmin[node]=min(cmin[node<<1],cmin[node<<1|1]);

}

void build(int node,int begin,int end)

{

    if(begin==end)

    {

         scanf("%d",&x);

         cmin[node]=x;

         a[begin]=x;

         return;

    }

    int m=(begin+end)>>1;

    build(node<<1,begin,m);

    build(node<<1|1,m+1,end);

    PushUp(node);

}

bool tag;

int minn;

int pos;

void query(int node,int begin,int end,int left,int right,int value)

{

    if(value<cmin[node])

        return;

    if(begin==end)

    {

        minn=cmin[node];

        pos=begin;

        tag=true;

        return;

    }

    int m=(begin+end)>>1;

    if(left<=m)

        query(node<<1,begin,m,left,right,value);

    if(tag) return;

    if(right>m)

        query(node<<1|1,m+1,end,left,right,value);

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        build(1,1,n);

        scanf("%d",&m);

        for(int i=1;i<=m;i++)

        {

            scanf("%d%d",&l,&r);

            tag=false;

            int x=a[l];

            if(l==r)

            {

                printf("%d\n",x);

                continue;

            }

            query(1,1,n,l+1,r,x);

            if(!tag)

                printf("%d\n",x);

            else

            {

                while(1)

                {

                    tag=false;

                    x%=minn;

                    if(pos+1>r)

                    {

                        printf("%d\n",x);

                        break;

                    }

                    query(1,1,n,pos+1,r,x);

                    if(!tag)

                    {

                        printf("%d\n",x);

                        break;

                    }

                }

            }

        }

    }

    return 0;

}