思路：
由于区间GCD的单调性，我们显然是在[L,R]之间选择一个数a[i]使得 d = gcd(x,a[i])最大，而d一定是x的一个因子。考虑到1e5之内的因子不算多(可以用约数个数去算一下，最多应该是100左右).我们将x的所有因子求出来。
然后从最大的因子开始枚举。接下来任务就变成了在区间[L,R]间查询是否存在一个数，他里面有因子g.我们可以预处理p[i]中存放代表1 ~ n 内 哪些位置出现了因子i.然后查询的时候二分查找即可。
思路：
由于区间GCD的单调性，我们显然是在[L,R]之间选择一个数a[i]使得 d = gcd(x,a[i])最大，而d一定是x的一个因子。考虑到1e5之内的因子不算多(可以用约数个数去算一下，最多应该是100左右).我们将x的所有因子求出来。
然后从最大的因子开始枚举。接下来任务就变成了在区间[L,R]间查询是否存在一个数，他里面有因子g.我们可以预处理p[i]中存放代表1 ~ n 内 哪些位置出现了因子i.然后查询的时候二分查找即可。
牛客博客，记录你的成长
京公网安备 11010502036488号