考虑枚举$k$的倍数$dk$，容易知道$\left \lceil \frac{L}{K} \right \rceil\leq d\leq \left \lfloor \frac{H}{k} \right \rfloor$

我们设全部$n$个数含有公因子$dk$且全部数互不相同的方案数是$f(d)$，记$x = (\left \lceil \frac{L}{K} \right \rceil - \left \lfloor \frac{H}{k} \right \rfloor + 1)$

　　　　那么$f(d) = (x^{n} - x)$

但是这样不是完全对的，因为这样子相当于把最大公因数是$2k,3k...$的情况也考虑进去了，我们最后还要容斥掉$f(2) f(3)...$这些数

其实就是一个莫比乌斯函数啦……线性筛一波

答案$ans = \sum_{i = 1}^{x - 1}f_{i} * \mu _{i}$

最后注意当$\left \lceil \frac{L}{K} \right \rceil$为$1$的时候，全部都选1也是一种可行的方案。

时间复杂度$O(nlogn)$

Code：

#include 
      
       using namespace std;typedef long long ll;const int N = 1e5 + 5;const ll P = 1e9 + 7;int n, ln, rn, k, pCnt = 0, pri[N];ll mu[N], f[N];bool np[N];inline ll pow(ll x, ll y) {    ll res = 1;    for(; y > 0; y >>= 1) {        if(y & 1) res = res * x % P;        x = x * x % P;    }    return res;}inline void sieve() {    mu[1] = 1LL;    for(int i = 2; i <= rn - ln; i++) {        if(!np[i]) {            mu[i] = -1LL;            pri[++pCnt] = i;        }        for(int j = 1; j <= pCnt && pri[j] * i <= rn - ln; j++) {            np[i * pri[j]] = 1;            if(i % pri[j] == 0) break;            else mu[i * pri[j]] = -mu[i];        }    } }int main() {    scanf("%d%d%d%d", &n, &k, &ln, &rn);    /*    if(ln % k) ln = ln / k + 1;     else ln /= k; */    ln = (ln + k - 1) / k, rn /= k;    if(ln > rn) return puts("0"), 0;        sieve();        for(int i = 1; i <= rn - ln; i++) {        int l = ln, r = rn;/*        if(l % i) l = l / i + 1;         else l /= i;  */        l = (l + i - 1) / i, r /= i;        if(l > r) continue;        f[i] = (pow(r - l + 1, n) - (r - l + 1) + P) % P;    }        ll ans = 0;    for(int i = 1; i <= rn - ln; i++)        ans = (ans + f[i] * mu[i] % P + P) % P;            if(ln == 1) ans = (ans + 1LL) % P;    printf("%lld\n", ans);    return 0;}