题解 | #整除问题#

#
# 寻找所有能整除 2021 的数对个数
# @param a long长整型 
# @param b long长整型 
# @param c long长整型 
# @param d long长整型 
# @return long长整型
#
class Solution:
    def __get_num(self, a, b, t):
        # [1, a)有多少个t倍数
        cnt_1_a_t = (a-1) // t
        # [1, b] 有多少个t倍数
        cnt_1_b_t = b // t
        return cnt_1_b_t - cnt_1_a_t

    def __get_same_num(self, a, b, c, d, tt):
        # 边界条件
        if b < c:
            return 0
        left = max(a, c)
        right = min(b, d)
        return self.__get_num(left, right, tt)
    def findPairs(self , a , b , c , d ):
        # write code here
        # 边界条件
        if a > c:
            a, b, c, d = c, d, a, b

        # 求[a, b], 有多少个43的倍数，有多少个47的倍数， 有多少个43*47的倍数
        cnt_a_b_43 = self.__get_num(a, b, 43)
        cnt_a_b_47 = self.__get_num(a, b, 47)
        cnt_a_b_2021 = self.__get_num(a, b, 2021)

        cnt_c_d_43 = self.__get_num(c, d, 43)
        cnt_c_d_47 = self.__get_num(c, d, 47)
        cnt_c_d_2021 = self.__get_num(c, d, 2021)

        cnt_a_b_c_d_2021 = self.__get_same_num(a, b, c, d, 2021)

        rnt = (cnt_a_b_43 - cnt_a_b_2021) * (cnt_c_d_47 - cnt_c_d_2021) + \
              (cnt_a_b_47 - cnt_a_b_2021) * (cnt_c_d_43 - cnt_c_d_2021) + \
              cnt_a_b_2021 * (d-c+1 - cnt_a_b_c_d_2021) + \
              cnt_c_d_2021 * (b-a+1 - cnt_a_b_c_d_2021) + \
              cnt_a_b_c_d_2021**2
        return rnt