HDU5726 GCD（rmq+二分）

这道题是2016第一场多校的1004，趁机优化了一发

题意：10W长度的数组，10W个询问，让你回答任意两点间的gcd和全局相同gcd的数量

思路：用由于gcd一段固定以后具有单调性的，用rmq nlogn预处理出所有gcd

然后用二分遍历枚举所有gcd的个数，存在mp里

然后对于每次询问，用nlogn的时间找到对应的gcd，在映射一下mp就可以了

/* *********************************************** Author :devil Created Time :2016/7/20 13:12:42 ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; typedef long long LL; const int N=1e5+10; int dp[N][20],mm[N],n,t,q; map<int,LL>mp; void initrmq() {mm[0]=-1;for(int i=1; i<=n; i++)mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];for(int j=1; j<=mm[n]; j++)for(int i=1; i+(1<<j)-1<=n; i++)dp[i][j]=__gcd(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } int rmq(int x,int y) {int k=mm[y-x+1];return __gcd(dp[x][k],dp[y-(1<<k)+1][k]); } int main() {//freopen("in.txt","r",stdin);scanf("%d",&t);for(int cas=1; cas<=t; cas++){scanf("%d",&n);for(int i=1; i<=n; i++)scanf("%d",&dp[i][0]);initrmq();mp.clear();for(int i=1; i<=n; i++){int l=i,r=n,mid,vs,tmp;while(1){tmp=l;vs=rmq(i,l);while(l<=r){mid=(l+r)>>1;if(rmq(i,mid)<vs) r=mid-1;else l=mid+1;}mp[vs]+=1ll*(r-tmp+1);r=n;if(l>r) break;}}int l,r;printf("Case #%d:\n",cas);scanf("%d",&q);while(q--){scanf("%d%d",&l,&r);int vs=rmq(l,r);printf("%d %lld\n",vs,mp[vs]);}}system("pause");return 0; }

 

转载于:https://www.cnblogs.com/d-e-v-i-l/p/5687979.html

总结

以上是生活随笔为你收集整理的HDU5726 GCD（rmq+二分）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。