题解 | #倍集#

这道题看了其他大佬的题解才看出来，首先就是需要让每一个独立的区间内部没有倍数，这可以通过收缩左边界实现。

然后假设全要，这个时候需要的就是找出和没有倍数关系的有几个。

我们从开始枚举，我们要满足 ，也就是乘一个倍数过后，仍然小于d。那么可以反解出k。

然后我们又需要让,那么最大的一个数就是,个数就是.

然后类似数论分块那样到下一个倍数k的区间即可。

理解如果有误欢迎大佬指正

import sys
read = sys.stdin.readline
if __name__ == "__main__":
    a,b,c,d = map(int,read().split())
    a = max(a,b // 2 + 1)
    c = max(c,d // 2 + 1)
    res = d - c + 1
    left = a 
    while left <= b:
        # k * left <= d
        k = d // left 
        #k倍为一个区间，找这个区间里面的,也就是[a,b]里面的x,x * k < c  
        right = min(b,(c - 1) // k)
        if left <= right:
            res += right - left + 1
        #类似数论分块，将这一坨都是k倍的跳过了。
        left = d // k + 1
    print(res)