HDU 5875 Function

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

(l,r), output 

F(l,r)

Sample Input

1

3

2 3 3

1

1 3

Sample Output

2

求一個區間最左端的數對于右端的全部數字取模，由于每次取模至少減半，是以取模的次數不會很多，

用線段樹來尋找右端小于等于目前值的第一個數字即可。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,int>
#define in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-8;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int T, n, m,l,r;
int a[N],f[N<<2];

void build(int x,int l,int r)
{
    if (l==r) {in(f[x]); a[l]=f[x];}
    else 
    {
        int mid=l+r>>1;
        build(lson); build(rson);
        f[x]=min(f[x<<1],f[x<<1|1]);
    }
}

int find(int x,int l,int r,int ll,int rr,int u)
{
    if (f[x] > u) return rr+1;
    if (ll<=l&&r<=rr)
    {
        if (l==r) return l;
        int mid=l+r>>1;
        if (f[x<<1]<=u) return find(lson,ll,rr,u);
        else return find(rson,ll,rr,u);
    }
    else 
    {
        int mid=l+r>>1,res;
        if (ll<=mid)
        {
            res=find(lson,ll,rr,u);
            if (res<=rr) return res;
        }
        if (rr>mid) 
        {
            res=find(rson,ll,rr,u);
            if (res<=rr) return res;
        }
        return rr+1;
    }
}

int main()
{
    in(T);
    while (T--)
    {
        scanf("%d",&n);
        build(1,1,n);
        scanf("%d",&m);
        while (m--)
        {
            scanf("%d%d",&l,&r);
            int ans=a[l];
            while (l < r)
            {
                int q = find(1,1,n,l+1,r,ans);
                if (q<=r) ans%=a[q];    l=q;
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}