Function HDU - 5875 —— 线段树求取模

本文主要是介绍Function HDU - 5875 —— 线段树求取模，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你一个数组，每次问你在区间l，r中a[l]%a[l+1]%a[l+2]%…a[r]是多少。

题解：

用线段树就好了，每次查询这个区间内第一个小于等于当前余数的值即可。为什么这样是对的。
首先是时间复杂度的问题,假设a>=b,a%b=c，那么c<=a/2恒成立。所以时间复杂度是$O(nlog{n}^2)$。
接下来是为什么要查询第一个小于等于当前的余数的问题，首先：6%4%3=2,但是6%3%4=0，所以顺序是不能变的，那么经过比它小的模数之后这个值必然会变，所以必须要查第一个小于等于它的模数。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int mi[N*4],a[N];
void build(int l,int r,int root)
{if(l==r){mi[root]=a[l];return ;}int mid=l+r>>1;build(l,mid,root<<1);build(mid+1,r,root<<1|1);mi[root]=min(mi[root<<1],mi[root<<1|1]);
}
int query(int l,int r,int root,int ql,int qr,int val)
{if(l==r)return mi[root];if(l>=ql&&r<=qr){int mid=l+r>>1;if(mi[root<<1]<=val)return query(l,mid,root<<1,ql,qr,val);return query(mid+1,r,root<<1|1,ql,qr,val);}int mid=l+r>>1;int ans=2e9;if(mid>=ql)ans=query(l,mid,root<<1,ql,qr,val);if(ans<=val)return ans;if(mid<qr)return query(mid+1,r,root<<1|1,ql,qr,val);return 2e9;
}
int main()
{int t;while(~scanf("%d",&t)){while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,n,1);int q;scanf("%d",&q);while(q--){int l,r;scanf("%d%d",&l,&r);if(l==r||!a[l])printf("%d\n",a[l]);else{int v=a[l];while(1){int x=query(1,n,1,l+1,r,v);if(x>v)break;v%=x;if(!v)break;}printf("%d\n",v);}}}}return 0;
}

这篇关于Function HDU - 5875 —— 线段树求取模的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---