首页 > 代码库 > hdu-5875
hdu-5875
题目大意:
f(l,r)=a[l] l==r
f(l,r)=f(l,r-1)%a[r] l<r
思路: 由此可以推出f(l,r)=a[l]%a[l+1]%a[l+2]%....%a[r]
根据取余的性质，只要后面取余的数不小于前面的数值不会改变,因此我们只要记录比a[l]小的第一个数，假如为a[x]然后接着找比a[x]小的第一个数
记为a[y] 如此一直找下去直到a[r]
代码如下:
#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define MAX 100005int n,q,a[MAX],nex[MAX];//n 数组的个数，q次查询,nex[i]=j代表a[j]是第一个小于a[i]的数int main(){ freopen("in.txt","r",stdin); int T; scanf("%d",&T); while(T--) { scanf("%d",&n); memset(nex,-1,sizeof(nex)); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(a[i]>a[j]) { nex[i]=j; break; } scanf("%d",&q); int l,r; while(q--) { scanf("%d%d",&l,&r); int ans = a[l]; int temp = l; while(nex[temp]<=r&&nex[temp]!=-1) { temp = nex[temp]; ans = ans%a[temp]; } printf("%d\n",ans); } }}
hdu-5875
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。