Function
Time Limit: 7000/3500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 399 Accepted Submission(s): 151
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).
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.
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
Source
//2016.9.11
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 100005 using namespace std; int a[N], nex[N];//nex数组，表示跳到下一个要取余的位置，比a[i]大的数不用取余，此处优化降低时间 int main()
{
int T, n, q, ans;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = ; i <= n; i++)
{
scanf("%d", &a[i]);
}
scanf("%d", &q);
int l, r;
for(int i = ; i <= n; i++)
{
nex[i] = -;
for(int j = i+; j <= n; j++)
if(a[i]>=a[j])
{
nex[i] = j;
break;
}
}
while(q--)
{
scanf("%d%d", &l, &r);
ans = a[l];
for(int i = nex[l]; i <= r; i = nex[i])
{
if(i == -)break;
ans %= a[i];
}
printf("%d\n", ans);
}
} return ;
}