题解 | 计数问题

import sys
import math
from math import gcd

# 计算两个数的最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)


# 计算一个列表所有数的最小公倍数
def multi_lcm(nums):
    res = 1
    for num in nums:
        res = lcm(res, num)
    return res


def solve():
    data = sys.stdin.read().split()
    idx = 0
    T = int(data[idx])
    idx += 1
    for _ in range(T):
        n, L, R = map(int, data[idx : idx + 3])
        idx += 3
        a = list(map(int, data[idx : idx + n]))
        idx += n
        a = list(set(a))  # 去重，减少子集数量
        n = len(a)
        ans = 0
        # 枚举所有非空子集，用二进制位表示：1~(1<<n)-1
        for mask in range(1, 1 << n):
            subset = []
            cnt = 0  # 子集的元素个数
            for i in range(n):
                if mask & (1 << i):
                    subset.append(a[i])
                    cnt += 1
            # 计算子集的最小公倍数
            m = multi_lcm(subset)
            if m > R:
                continue  # 无满足条件的数，剪枝
            # 区间内能被m整除的数的个数
            num = R // m - (L - 1) // m
            # 容斥：奇数加，偶数减
            if cnt % 2 == 1:
                ans += num
            else:
                ans -= num
        print(ans)


if __name__ == "__main__":
    solve()