HDU 5726 GCD (RMQ+二分)

HDU 5726 GCD (RMQ+二分)

题目链接:点我~~ 题意:给你n个数,m个询问,每次询问某个区间,求这段区间所有数的gcd,然后问1~n所有连续区间中gcd的值等于区间所有数gcd的个数~~ 思路:对于求区间gcd可以用线段树维护,或者RMQ,因为后者的查询是O(1)~还是比较方便的。对于所有区间的gcd,考虑枚举左端点,二分区间进行预处理~例如12467,以1为左端点,1~5为右端点5个...
07月20日 254
  1. .01
  2. .02