题解 P3172 【[CQOI2015]选数】

caeious · 2020-08-16 17:32:02 · 题解

记 D = H - L.

这题有两种常规做法：一种是 \mathcal{O}(H^{\frac{2}{3}}) 杜教筛，另一种是 \mathcal{O}(D \log D + D \log n) 的容斥。然而杜教筛完全没有用到 D 较小的条件，~~并且不适合该算法还没普及的 CQOI2015~~，容斥是组合而不是数论方法，~~不如推莫反式子来的优美~~。因此，本文给出一种纯数论的 \mathcal{O}(D + \sqrt{D} \log n) 做法。

不失一般性（这一步怎么推导参见其他任何一篇题解），将原问题变为：

求从 (l,r] 中选取 N 个整数 i_1, i_2, \dots, i_n，它们的最大公约数等于 1 的方案数。
重定义 D = r - l.

不难发现所求

\begin{aligned} &= \sum_{i_1 \in (l, r]} \sum_{i_2 \in (l, r]} \dots \sum_{i_n \in (l, r]}[(i_1, i_2, \dots, i_n) = 1] \\ &= \sum_{i_1 \in (l, r]} \sum_{i_2 \in (l, r]} \dots \sum_{i_n \in (l, r]}\sum_{d | (i_1, i_2, \dots, i_n)} \mu(d) && (\mu \ast 1 = \epsilon) \\ &= \sum_{d = 1}^r \mu(d) \sum_{\begin{aligned} i_1 \in &(l, r] \\ d &| i_1 \end{aligned}} \dots \sum_{\begin{aligned} i_n \in &(l, r] \\ d &| i_n \end{aligned}}1 && (\text{先枚举 $d$, 并将 $\mu(d)$ 提出}) \\ &= \sum_{d = 1}^r \mu(d)(\lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor)^n && (\text{$(l, r]$ 中 $d$ 的倍数有 $\lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor$ 个}) \end{aligned}

当 d > D 时，\lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor = 0 或 1，故 (\lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor) ^ n = \lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor.

将原式拆开

\begin{aligned} &= \sum_{d = 1}^D\mu(d)(\lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor)^n + \sum_{d = D + 1}^r \mu(d)(\lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor) \end {aligned}

右边这一项

\begin{aligned} &= \sum_{d = D + 1}^r \sum_{\begin{aligned} i \in &(l, r] \\ d &| i \end{aligned}} \mu(d) && (\text{$(l, r]$ 中 $d$ 的倍数有 $\lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor$ 个, 并将 $\mu(d)$ 乘进去}) \\ &= \sum_{d = 1}^r \sum_{\begin{aligned} i \in &(l, r] \\ d &| i \end{aligned}} \mu(d) - \sum_{d = 1}^D \sum_{\begin{aligned} i \in &(l, r] \\ d &| i \end{aligned}} \mu(d) && (差分) \\ &= \sum_{i \in (l, r]} \sum_{d | i} \mu(d) - \sum_{d = 1}^D \mu(d) \sum_{\begin{aligned} i \in &(l, r] \\ d &| i \end{aligned}} 1 && (\text{左边一项先枚举 $i$, 右边一项提出 $\mu(d)$}) \\ &= \sum_{i = l + 1}^r \epsilon(i) - \sum_{d = 1}^D\mu(d)(\lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor) &&(\mu \ast 1 = \epsilon \text{, $(l, r]$ 中 $d$ 的倍数有 $\lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor$ 个}) \\ &= \epsilon(l + 1) - \sum_{d = 1}^D\mu(d)(\lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor) && (l + 2 > 1) \end {aligned}

所以总的答案

\begin{aligned} &= \sum_{d = 1}^D\mu(d)(\lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor)^n + \epsilon(l + 1) - \sum_{d = 1}^D\mu(d)(\lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor) \\ &= \sum_{d = 1}^D\mu(d)[(\lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor)^n - (\lfloor\dfrac{r}{d}\rfloor - \lfloor \dfrac{l}{d}\rfloor)] + \epsilon(l + 1) \end{aligned}

左边这个和式，\mathcal{O}(D) 线性筛处理 \mu 前缀和，再 \mathcal{O}(\sqrt{D} \log n) 数论分块。

Sample Code

注：由于本题数据范围较小，该代码并没有使用线性筛和数论分块

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <utility>
#include <queue>
using namespace std;
typedef long long ll;
typedef long double ldouble;
const int LEN = 100000;

struct fastio {
  int it, len;
  char s[LEN + 5];
  fastio() {
    it = len = 0;
  }
  char get() {
    if (it < len) return s[it++];
    it = 0, len = fread(s, 1, LEN, stdin);
    return len ? s[it++] : EOF;
  }
  bool notend() {
    char c;
    for (c = get(); c == ' ' || c == '\n' || c == '\r'; c = get());
    if (it) it--;
    return c != EOF;
  }
  void put(char c) {
    if (it == LEN) fwrite(s,1,LEN,stdout), it = 0;
    s[it++] = c;
  }
  void flush() {
    fwrite(s, 1, it, stdout);
  }
}buff, bufo;
inline int getint() {
  char c; int res = 0, sig = 1;
  for (c = buff.get(); c < '0' || c > '9'; c = buff.get()) if(c == '-') sig = -1;
  for (; c >= '0' && c <= '9'; c = buff.get()) res = res * 10 + (c - '0');
  return sig * res;
}
inline ll getll() {
  char c; ll res = 0, sig = 1;
  for (c = buff.get(); c < '0' || c > '9'; c = buff.get()) if (c == '-') sig = -1;
  for (; c >= '0' && c <= '9'; c = buff.get()) res = res * 10 + (c - '0');
  return sig * res;
}
inline void putint(int x, char suf) {
  if (!x) bufo.put('0');
  else {
    if (x < 0) bufo.put('-'), x = -x;
    int k = 0; char s[15];
    while (x) {
      s[++k] = x % 10 + '0';
      x /= 10;
    }
    for (; k; k--) bufo.put(s[k]);
  }
  bufo.put(suf);
}
inline void putll(ll x, char suf) {
  if (!x) bufo.put('0');
  else {
    if (x < 0) bufo.put('-'), x = -x;
    int k = 0; char s[25];
    while (x) {
      s[++k] = x % 10 + '0';
      x /= 10;
    }
    for (; k; k--) bufo.put(s[k]);
  }
  bufo.put(suf);
}
inline char get_char() {
  char c;
  for (c = buff.get(); c == ' ' || c == '\n' || c == '\r'; c = buff.get());
  return c;
}

#define mod 1000000007
ll modpow(ll x, ll y) {
  ll res = 1;
  while (y) {
    if (y & 1) res = res * x % mod;
    y >>= 1;
    x = x * x % mod;
  }
  return res;
}

int n, k, L, H, l, r, mu[100005], ans;

int main() {
  n = getint(), k = getint(), L = getint(), H = getint();
  l = (L - 1) / k, r = H / k;
  mu[1] = 1;
  for (int i = 1; i <= 100000; i++) {
    for (int j = i << 1; j <= 100000; j += i) {
      mu[j] -= mu[i];
    }
  }
  if (r <= 100000) {
    for (int d = 1; d <= r; d++)
      (ans += mu[d] * modpow(r / d - l / d, n)) %= mod;
    putll((ans + mod) % mod, '\n');
  } else {
    for (int d = 1; d <= 100000; d++)
      (ans += mu[d] * modpow(r / d - l / d, n)) %= mod;
    (ans += (l == 0)) %= mod;
    for (int d = 1; d <= 100000; d++)
      (ans -= (r / d - l / d) * mu[d]) %= mod;
    putll((ans + mod) % mod, '\n');
  }
  bufo.flush();
  return 0;
}

Note

对于容斥的做法，核算容斥系数也可以得到相同的式子。