1. 首页
  2. RMQ, 二分

HDU 5726 GCD (RMQ+二分)

题目链接:点我~~

题意:给你n个数,m个询问,每次询问某个区间,求这段区间所有数的gcd,然后问1~n所有连续区间中gcd的值等于区间所有数gcd的个数~~

思路:对于求区间gcd可以用线段树维护,或者RMQ,因为后者的查询是O(1)~还是比较方便的。对于所有区间的gcd,考虑枚举左端点,二分区间进行预处理~例如12467,以1为左端点,1~5为右端点5个gcd都是1,其实只要算一次就可以了,然后看以这个为左端点的区间有哪些值,并且把区间长度算出来就行了。

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/1052 (转载时请注明本文出处及文章链接)
上一篇:
:下一篇

1 条评论

gravatar

  1. 小包子 2016-08-06 Google Chrome 52.0.2743.82Windows 10

    :smile: 摸了线段树能看懂题解,看懂了觉得是水题。

    回复 沙发
  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40