自动搬运

查看原文

来自洛谷，原作者为

	xyz32768 “各方面相差太远”

搬运于2025-08-24 21:46:05，当前版本为作者最后更新于2017-10-22 10:53:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，进行如下处理：

1、如果$L$是$K$的倍数，那么把$L$变为$\frac{L}{K}$，否则变为$\lfloor\frac{L}{K}\rfloor+1$。

2、把$H$变成$\lfloor\frac{H}{K}\rfloor$。

这样子容易得出，现在要求的就是在$[L,H]$之间，选数$N$次使选出的数最大公约数为$1$的方案数。

现在，用$f[i]$表示选出的数的最大公约数$i$且选出的数不全相同的方案数。此时先求出$[L,H]$之间$i$的倍数的个数$x$，暂时令$f[i]=x^N-x$。

但此时得到的$f[i]$实际上是含有公约数$i$的方案数，不是最大公约数为$i$的方案数。但是可以发现，此时的$f[i]$包含有最大公约数为$i,2i,3i,...$的方案数。这时候使用容斥原理：假设已经知道了$f[2i],f[3i],...$的最终结果，那么就把$f[i]$分别减去$f[2i],f[3i],...$，就可以得到$f[i]$的最终结果。倒着推一遍。

特殊情况：$L=1$时可以所有的数都选$1$。所以$L=1$时答案要加$1$。

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
const int N = 1e5 + 5, PYZ = 1e9 + 7;
int n, K, L, H, f[N];
int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % PYZ;
        a = 1ll * a * a % PYZ;
        b >>= 1;
    }
    return res;
}
int main() {
    int i, j; n = read(); K = read(); L = read(); H = read();
    if (L % K) L = L / K + 1; else L /= K; H /= K;
    if (L > H) return puts("0"), 0;
    for (i = 1; i <= H - L; i++) {
        int l = L, r = H;
        if (l % i) l = l / i + 1; else l /= i; r /= i;
        if (l > r) continue;
        f[i] = (qpow(r - l + 1, n) - (r - l + 1) + PYZ) % PYZ;
    }
    for (i = H - L; i; i--) for (j = (i << 1); j <= H - L; j += i)
        f[i] = (f[i] - f[j] + PYZ) % PYZ;
    if (L == 1) (f[1] += 1) %= PYZ; cout << f[1] << endl;
    return 0;
}