HDU5875 Function

**题意：**给定序列，有m个区间的询问，求每个询问a[l]%a[l+1]...%a[r]后的值。（N
/** @Date    : 2016-11-19-16.07


  * @Author  : Lweleth (SoungEarlf@gmail.com)


  * @Link    : https://github.com/


  * @Version :


  */


#include <stdio.h>


#include <iostream>


#include <string.h>


#include <algorithm>


#include <utility>


#include <vector>


#include <map>


#include <set>


#include <string>


#include <stack>


#include <queue>


//#include<bits/stdc++.h>


#define LL long long


#define MMF(x) memset((x),0,sizeof(x))


#define MMI(x) memset((x), INF, sizeof(x))


using namespace std;





const int INF = 0x3f3f3f3f;


const int N = 1e5+2000;





int a[N];


int np[N];





int main()


{


    int T;


    int n, q;


    while(~scanf("%d", &T))


    {


        while(T--)


        {





            scanf("%d", &n);


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


                scanf("%d", a + i);


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


            {


                np[i] = -1;


                for(int j = i + 1; j <= n; j++)


                {


                    if(a[j] <= a[i])//


                    {


                        np[i] = j;


                        break;


                    }


                }


            }


            scanf("%d", &q);


            int l, r;





            while(q--)


            {


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


                int ans = a[l];


                for(int i = np[l]; i <= r; i = np[i])


                {


                    if(i == -1 || ans == 0)


                        break;


                    ans %= a[i];


                }


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


            }


        }


    }


    return 0;


}
巴特西

HDU5875 Function

最新文章

热门文章
