题目重述

从区间 $[L, H]$ 中选取 $N$ 个整数（可重复），求这些数的最大公约数恰好为 $K$ 的方案数，结果对 $10^9+7$ 取模。

关键思路

问题转换

设选出的数为 $a_1, a_2, \dots, a_N$，则 $\gcd(a_1, \dots, a_N) = K$ 等价于：

所有 $a_i$ 都是 $K$ 的倍数

设 $b_i = a_i / K$，则 $\gcd(b_1, \dots, b_N) = 1$

区间变换

令：$l' = \lceil L/K \rceil$, $h' = \lfloor H/K \rfloor$ 如果 $l' > h'$，则没有符合条件的数，答案为 $0$。

否则，问题转化为：在区间 $[l', h']$ 中选 $N$ 个整数 $x_1, \dots, x_N$，使得 $\gcd(x_1, \dots, x_N) = 1$ 的方案数。

容斥原理与莫比乌斯反演

定义函数

设 $F(d)$ 表示 $\gcd$ 是 $d$ 的倍数 的方案数。

区间 $[l', h']$ 中 $d$ 的倍数的个数为： $\text{cnt}(d) = \left\lfloor \frac{h'}{d} \right\rfloor - \left\lceil \frac{l'}{d} \right\rceil + 1$

即： $\text{cnt}(d) = \frac{h'}{d} - \frac{l'+d-1}{d} + 1$

因此： $F(d) = (\text{cnt}(d))^N$

莫比乌斯反演

设 $f(d)$ 表示 $\gcd$ 恰好等于 $d$ 的方案数。

设 $f(d)$ 表示 $\gcd$ 恰好等于 $d$ 的方案数。

那么： $F(d) = \sum_{d|m} f(m)$

由莫比乌斯反演： $f(d) = \sum_{d|m} \mu(m/d)F(m)$

我们要求的是 $f(1)$，即： $f(1) = \sum_{m=1}^{h'} \mu(m)F(m)$

算法实现

代码思路

1.预处理：计算 $l' = \lceil L/K \rceil$，$h' = \lfloor H/K \rfloor$

2.特殊情况：如果 $l' > h'$，输出 $0$

3.计算 $F(d)$：对于每个 $d$，计算区间内 $d$ 的倍数的个数 $x$，然后 $f[d] = x^N - x$（减去所有数相同的情况）

4.容斥计算：从大到小枚举 $d$，减去 $f[j]$（其中 $j$ 是 $d$ 的倍数）

5.特殊处理：如果 $l' = 1$，加上所有数都取 $1$ 的情况

复杂度分析

区间长度 $h' - l' \leq 10^5$，循环在 $O((h'-l') \log (h'-l'))$ 内完成，可以接受。

总结

本题通过除以 $K$ 将问题转化为 $\gcd=1$ 的情况，利用区间倍数个数和容斥原理（或莫比乌斯反演）求解，能够高效处理 $H-L \leq 10^5$ 的大范围 $N,K$ 情况。