P3172 [CQOI2015]选数

考虑每次选择 $K$ 的倍数的方法有 $G(K) =(\frac R K - \frac {L - 1} K) ^ N$ 种。我们要求刚好为 $K$ ，即
$$
G(K) = \sum _ {n | d} f(d)
$$
上莫反，
$$
\begin {aligned}
f(K)& = \sum _ {n | d} \mu(\frac nd) G(d) \\
& = \sum _ {d = 1} ^ \infty \mu(d) G(nd)
\end {aligned}
$$
$\infty$ 最多需要算到 $\frac R m$ ，所以可以达到 $10 ^ 9$ ，所以要数论分块和杜教筛。

查看代码

#include <cstdio>
#include <map>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
typedef long long LL;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, m, L, R, f[N];
map <int, int> F;
int cnt, p[N];
bool vis[N];
void init()
{
    f[1] = 1;
    vis[1] = true;
    for (int i = 2; i < N; ++i)
    {
        if (!vis[i]) p[++cnt] = i, f[i] = -1;
        for (int j = 1; i * p[j] < N; ++j)
        {
            vis[i * p[j]] = true;
            if (i % p[j] == 0)
                { f[i * p[j]] = 0; break; }
            f[i * p[j]] = f[i] * f[p[j]];
        }
    }
    for (int i = 2; i < N; ++i) f[i] += f[i - 1];
}
int calc (int x)
{
    if (x < N) return f[x];
    if (F.count(x)) return F[x];
    int res = 1;
    for (int l = 2, r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        res -= (r - l + 1) * calc(x / l);
    }
    return F[x] = res;
}
int binpow (int b, int k = n)
{
    int res = 1;
    for (; k; k >>= 1, b = (LL)b * b % mod)
        if (k & 1) res = (LL)res * b % mod;
    return res;
}
int main ()
{
    init();
    read(n, m, L, R);
    L = (L - 1) / m, R = R / m;
    int res = 0;
    for (int l = 1, r; l <= R; l = r + 1)
    {
        r = !(L / l) ? R / (R / l) : min(L / (L / l), R / (R / l));
        (res += (LL)(calc(r) - calc(l - 1)) * binpow(R / l - L / l) % mod) %= mod;
    }
    write((res + mod) % mod);
    return 0;
}