首页 > 代码库 > 2016大连网络赛 Function

2016大连网络赛 Function

2024-08-12 22:38:31   223人阅读

Function

Time Limit: 7000/3500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)


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
132 3 311 3
 

 

Sample Output
2
分析：暴力转移即可；（此方法复杂度高，待改进，不过能A。。。）
　　　参考http://blog.csdn.net/angon823/article/details/52496697
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <map>#include <queue>#include <stack>#include <vector>#include <list>#define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define Lson L, mid, rt<<1#define Rson mid+1, R, rt<<1|1const int maxn=1e5+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}int n,m,k,t,q,a[maxn],r[maxn];int main(){    int i,j;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        rep(i,1,n)scanf("%d",&a[i]);        memset(r,inf,sizeof r);        r[n]=inf;        for(i=n-1;i>=1;i--)        {            k=i+1;            while(k<=n)            {                if(a[i]>a[k])                {                    r[i]=k;                    break;                }                k=r[k];            }        }        scanf("%d",&q);        while(q--)        {            int x,y,ans;            scanf("%d%d",&x,&y);            ans=a[x];            while(r[x]<=y)            {                ans%=a[r[x]];                x=r[x];            }            printf("%d\n",ans);        }    }    //system("Pause");    return 0;}

2016大连网络赛 Function


联系
我们