首页 > 代码库 > HDU5875

HDU5875

2024-08-12 23:13:19   225人阅读

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).
 

 

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
 

Source

2016 ACM/ICPC Asia Regional Dalian Online
 
 1 //2016.9.11 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #define N 100005 6  7 using namespace std; 8  9 int a[N], nex[N];//nex数组，表示跳到下一个要取余的位置，比a[i]大的数不用取余，此处优化降低时间10 11 int main()12 {13     int T, n, q, ans;14     scanf("%d", &T);15     while(T--)16     {17         scanf("%d", &n);18         for(int i = 1; i <= n; i++)19         {20             scanf("%d", &a[i]);21         }22         scanf("%d", &q);23         int l, r;24         for(int i = 1; i <= n; i++)25         {26             nex[i] = -1;27             for(int j = i+1; j <= n; j++)28                 if(a[i]>=a[j])29                 {30                     nex[i] = j;31                     break;32                 }33         }34         while(q--)35         {36             scanf("%d%d", &l, &r);37             ans = a[l];38             for(int i = nex[l]; i <= r; i = nex[i])39             {40                 if(i == -1)break;41                 ans %= a[i];42             }43             printf("%d\n", ans);44         }45     }46 47     return 0;48 }

 

HDU5875


联系
我们