HDU 5869 Different GCD Subarray Query

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5869

题目翻译

给一个序列,求[L,R]区间内,有多少个不同的子区间的区间GCD

题解

首先计算不同的GCD,我们使用离线询问,然后用树状数组/线段树把不同数记录在最后一次出现位置的方法。
然后如何计算不同的GCD,则可以通过ST表+倍增 logN 的查找。

代码