Bỏ qua

Sàng Min_25

Định nghĩa

Từ tư tưởng phương pháp của loại sàng này, nó còn được gọi là "Extended Eratosthenes Sieve".

Do nó được Min_25 phát minh và sử dụng đầu tiên, nên gọi là "Min_25 Sàng".

Tính chất

Nó có thể giải quyết một lớp bài toán về hàm tích tính trong thời gian \(O\left(\frac{n^{\frac{3}{4}}}{\log{n}}\right)\) hoặc \(\Theta\left(n^{1 - \epsilon}\right)\).

Yêu cầu: \(f(p)\) là một hàm hoàn toàn tích tính có thể tính nhanh (ví dụ như đa thức); \(f(p^{c})\) có thể tính nhanh.

Ký hiệu

  • Nếu không nói gì thêm, tất cả các biến được gọi là \(p\) trong các phần này đều là các số nguyên tố.
  • \(x / y := \left\lfloor\frac{x}{y}\right\rfloor\)
  • \(\operatorname{isprime}(n) := [ |\{d : d \mid n\}| = 2 ]\) tức là \(n\) là số nguyên tố thì giá trị là \(1\), ngược lại là \(0\).
  • \(p_{k}\): số nguyên tố thứ \(k\) nhỏ nhất (ví dụ: \(p_{1} = 2, p_{2} = 3\)). Đặc biệt, đặt \(p_{0} = 1\).
  • \(\operatorname{lpf}(n) := [1 < n] \min\{p : p \mid n\} + [1 = n]\) tức là \(n\) có số nguyên tố nhỏ nhất. Đặc biệt, \(n=1\) thì giá trị là \(1\).
  • \(F_{\mathrm{prime}}(n) := \sum_{2 \le p \le n} f(p)\)
  • \(F_{k}(n) := \sum_{i = 2}^{n} [p_{k} \le \operatorname{lpf}(i)] f(i)\)

Giải thích

Quan sát định nghĩa \(F_{k}(n)\), ta thấy rằng đáp án là \(F_{1}(n) + f(1) = F_{1}(n) + 1\).

Xem xét cách tính \(F_{k}(n)\). Qua việc liệt kê từng \(i\) và số mũ nhỏ nhất của nó, ta có thể được công thức đệ quy:

\[ \begin{aligned} F_{k}(n) &= \sum_{i = 2}^{n} [p_{k} \le \operatorname{lpf}(i)] f(i) \\ &= \sum_{\substack{k \le i \\ p_{i}^{2} \le n}} \sum_{\substack{c \ge 1 \\ p_{i}^{c} \le n}} f\left(p_{i}^{c}\right) ([c > 1] + F_{i + 1}\left(n / p_{i}^{c}\right)) + \sum_{\substack{k \le i \\ p_{i} \le n}} f(p_{i}) \\ &= \sum_{\substack{k \le i \\ p_{i}^{2} \le n}} \sum_{\substack{c \ge 1 \\ p_{i}^{c} \le n}} f\left(p_{i}^{c}\right) ([c > 1] + F_{i + 1}\left(n / p_{i}^{c}\right)) + F_{\mathrm{prime}}(n) - F_{\mathrm{prime}}(p_{k - 1}) \\ &= \sum_{\substack{k \le i \\ p_{i}^{2} \le n}} \sum_{\substack{c \ge 1 \\ p_{i}^{c + 1} \le n}} \left(f\left(p_{i}^{c}\right) F_{i + 1}\left(n / p_{i}^{c}\right) + f\left(p_{i}^{c + 1}\right)\right) + F_{\mathrm{prime}}(n) - F_{\mathrm{prime}}(p_{k - 1}) \end{aligned} \]

Bước cuối cùng dựa trên một sự thật: với \(c\) sao cho \(p_{i}^{c} \le n < p_{i}^{c + 1}\), thì \(p_{i}^{c + 1} > n \iff n / p_{i}^{c} < p_{i} < p_{i + 1}\), nên \(F_{i + 1}\left(n / p_{i}^{c}\right) = 0\). Giá trị biên là \(F_{k}(n) = 0 (p_{k} > n)\).

Giả sử đã có tất cả các \(F_{\mathrm{prime}}(n)\), thì có hai cách để tính tất cả các \(F_{k}(n)\):

  1. Tính trực tiếp theo công thức đệ quy.
  2. Từ lớn đến nhỏ duyệt \(p\) chuyển tiếp, chỉ khi \(p^{2} < n\) thì giá trị tăng không phải là \(0\), nên có thể tối ưu hóa theo hậu tố.

Bây giờ xem xét cách tính \(F_{\mathrm{prime}}{(n)}\). Quan sát quá trình tính \(F_{k}(n)\), dễ thấy rằng \(F_{\mathrm{prime}}\) chỉ có \(O(\sqrt{n})\) điểm có giá trị hữu ích: \(1, 2, \dots, \left\lfloor\sqrt{n}\right\rfloor, n / \sqrt{n}, \dots, n / 2, n\). Thường thì \(f(p)\) là một đa thức bậc thấp, có thể biểu diễn thành \(f(p) = \sum a_{i} p^{c_{i}}\). Thì đối với mỗi \(p^{c_{i}}\), đóng góp vào \(F_{\mathrm{prime}}(n)\) là \(a_{i} \sum_{2 \le p \le n} p^{c_{i}}\). Phân tích từng \(p^{c_{i}}\) đóng góp, bài toán chuyển thành: cho \(n, s, g(p) = p^{s}\), đối với mọi \(m = n / i\), tính \(\sum_{p \le m} g(p)\).

Lưu ý

\(g(p) = p^{s}\) là hàm hoàn toàn tích tính!

Vậy đặt \(G_{k}(n) := \sum_{i = 2}^{n} \left[p_{k} < \operatorname{lpf}(i) \lor \operatorname{isprime}(i)\right] g(i)\), tức là tổng giá trị \(g\) của các số còn lại sau khi sàng thứ \(k\). Với một hợp số \(x \le n\), chắc chắn có \(\operatorname{lpf}(x) \le \sqrt{x} \le \sqrt{n}\). Đặt \(p_{\ell(n)}\) là số nguyên tố lớn nhất không vượt quá \(\sqrt{n}\), thì \(\sum_{2\le p\le n}g(p) = G_{\ell(n)}(n)\), tức là sau khi sàng \(\ell\) lần, còn lại toàn bộ là các số nguyên tố. Xem xét giá trị biên, rõ ràng là \(G_{0}(n) = \sum_{i = 2}^{n} g(i)\). Đối với chuyển tiếp, xem xét quá trình sàng, phân tích từng phần:

  1. Với \(n < p_{k}^{2}\), \(G\) không đổi, tức là \(G_{k}(n) = G_{k - 1}(n)\).
  2. Với \(p_{k}^{2} \le n\), các số bị sàng đều có thừa số nguyên tố \(p_{k}\), tức là \(-g(p_{k}) G_{k - 1}(n / p_{k})\).
  3. Với phần thứ hai, do \(p_{k}^{2} \le n \iff p_{k} \le n / p_{k}\), các \(i\) thỏa mãn \(\operatorname{lpf}(i) < p_{k}\) sẽ bị trừ đi. Phần này cần cộng lại, tức là \(g(p_{k}) G_{k - 1}(p_{k - 1})\).

Thì có:

\[ G_{k}(n) = G_{k - 1}(n) - \left[p_{k}^{2} \le n\right] g(p_{k}) (G_{k - 1}(n / p_{k}) - G_{k - 1}(p_{k - 1})) \]

Phân tích độ phức tạp

Với \(F_{k}(n)\), phương pháp thứ nhất có độ phức tạp \(O\left(n^{1 - \epsilon}\right)\) (xem zzt tập huấn 2.3);
Phương pháp thứ hai, thực chất là phần thứ hai của sàng Châu Gé, trong bài luận của Châu Gé cũng có đề cập (6.5.4), độ phức tạp được chứng minh là \(O\left(\frac{n^{\frac{3}{4}}}{\log{n}}\right)\).

Với \(F_{\mathrm{prime}}(n)\), thực tế, nó giống với phần đầu tiên của sàng Châu Gé. Xem xét với mỗi \(m = n / i\), chỉ có khi liệt kê các \(p_{k}\) thỏa mãn \(p_{k}^{2} \le m\) thì mới có đóng góp vào độ phức tạp, nên có thể ước lượng:

\[ \begin{aligned} T(n) &= \sum_{i^{2} \le n} O\left(\pi\left(\sqrt{i}\right)\right) + \sum_{i^{2} \le n} O\left(\pi\left(\sqrt{\frac{n}{i}}\right)\right) \\ &= \sum_{i^{2} \le n} O\left(\frac{\sqrt{i}}{\ln{\sqrt{i}}}\right) + \sum_{i^{2} \le n} O\left(\frac{\sqrt{\frac{n}{i}}}{\ln{\sqrt{\frac{n}{i}}}}\right) \\ &= O\left(\int_{1}^{\sqrt{n}} \frac{\sqrt{\frac{n}{x}}}{\log{\sqrt{\frac{n}{x}}}} \mathrm{d} x\right) \\ &= O\left(\frac{n^{\frac{3}{4}}}{\log{n}}\right) \end{aligned} \]

Về không gian, có thể thấy rằng cả \(F_{k}\) và \(F_{\mathrm{prime}}\) chỉ có giá trị hữu ích tại \(n / i\), tổng cộng \(O(\sqrt{n})\) điểm, chỉ cần ghi lại giá trị hữu ích là có thể tối ưu hóa không gian xuống \(O(\sqrt{n})\).

Trước hết, qua một lần phân tích số học, ta có thể tìm được tất cả các giá trị hữu ích, dùng một mảng \(\text{lis}\) kích thước \(O(\sqrt{n})\) để ghi lại. Với giá trị hữu ích \(v\), ghi \(\text{id}(v)\) là chỉ số trong \(\text{lis}\), dễ thấy rằng: với mọi giá trị hữu ích \(v\), \(\text{id}(v) \le \sqrt{n}\).

Sau đó phân tích riêng các giá trị hữu ích nhỏ hơn hoặc bằng \(\sqrt{n}\) và lớn hơn \(\sqrt{n}\): với giá trị hữu ích nhỏ hơn hoặc bằng \(\sqrt{n}\), dùng một mảng \(\text{le}\) để ghi lại \(\text{id}(v)\), tức là \(\text{le}_v = \text{id}(v)\); với giá trị hữu ích lớn hơn \(\sqrt{n}\), dùng một mảng \(\text{ge}\) để ghi lại \(\text{id}(v)\), do \(v\) quá lớn nên dùng \(v' = n / v < \sqrt{n}\) để ghi lại \(\text{id}(v)\), tức là \(\text{ge}_{v'} = \text{id}(v)\).

Vậy ta có thể dùng hai mảng kích thước \(O(\sqrt{n})\) để ghi lại tất cả các giá trị hữu ích của \(\text{id}\) và \(O(1)\) để truy vấn. Trong quá trình tính \(F_{k}\) hoặc \(F_{\mathrm{prime}}\), dùng chỉ số \(\text{id}\) thay cho giá trị hữu ích, có thể tối ưu hóa không gian xuống \(O(\sqrt{n})\).

Quá trình

Với \(F_{k}(n)\), ta thường chọn phương pháp đầu tiên vì độ khó thực hiện thấp, thường biểu hiện tốt hơn phương pháp thứ hai khi dữ liệu nhỏ.

Với \(F_{\mathrm{prime}}(n)\), thực hiện trực tiếp theo công thức đệ quy.

Với \(p_{k}^{2} \le n\) thì có thể dùng sàng tuyến tính để tính \(s_{k} := F_{\mathrm{prime}}(p_{k})\) thay cho \(F_{k}\) đệ quy trong \(F_{\mathrm{prime}}(p_{k - 1})\). Tương ứng, \(G\) đệ quy trong \(G_{k - 1}(p_{k - 1}) = \sum_{i = 1}^{k - 1} g(p_{i})\) cũng có thể dùng phương pháp này để tiền xử lý.

Dùng Extended Eratosthenes Sieve để tính hàm tích tính \(f\) trước, cần rõ ràng các điểm sau:

  • Cách sàng nhanh (thường là thời gian tuyến tính) các giá trị \(f\) trước \(\sqrt{n}\).
  • Biểu diễn đa thức của \(f(p)\).
  • Cách tính nhanh \(f(p^{c})\).

Rõ ràng các điểm trên, thực hiện theo thứ tự:

  1. Sàng \([1, \sqrt{n}]\) và các giá trị \(f\) trước \(\sqrt{n}\).
  2. Với mỗi hạng tử của đa thức \(f(p)\), sàng ra các \(G\), hợp lại thành \(F_{\mathrm{prime}}\) có \(O(\sqrt{n})\) điểm hữu ích.
  3. Thực hiện đệ quy theo \(F_{k}\), tính \(F_{1}(n)\).

Ví dụ

Luogu P4213【模板】杜教筛

Tính \(\displaystyle \sum_{i = 1}^{n} \varphi(i)\) và \(\displaystyle \sum_{i = 1}^{n} \mu(i)\).

Giải

Với \(\varphi(i)\), dễ thấy \(f(p) = p - 1\). Với \(f(p)\) bậc nhất \((p)\), có \(g(p) = p, G_{0}(n) = \sum_{i = 2}^{n} g(i) = \frac{(n + 2) (n - 1)}{2}\). Với \(f(p)\) bậc hằng \((-1)\), có \(g(p) = -1, G_{0}(n) = \sum_{i = 2}^{n} g(i) = -n + 1\). Sàng hai lần cộng lại là được \(F_{\mathrm{prime}}\) cần thiết.

Với \(\mu(i)\), dễ thấy \(f(p) = -1\). Có \(g(p) = -1, G_{0}(n) = \sum_{i = 2}^{n} g(i) = -n + 1\). Sàng trực tiếp là được \(F_{\mathrm{prime}}\) cần thiết.

LOJ 6053 简单的函数

Cho \(f(n)\):

\[ f(n) = \begin{cases} 1 & n = 1 \\ p \operatorname{xor} c & n = p^{c} \\ f(a)f(b) & n = ab \land a \perp b \end{cases} \]

Tính \(\displaystyle \sum_{i = 1}^{n} f(i)\).

Giải

Dễ thấy \(f(p) = p - 1 + 2[p = 2]\). Vậy sàng theo cách sàng \(\varphi\) là được, chỉ cần xét riêng \(2\).

Tham khảo code 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/* 「LOJ #6053」简单的函数 */
#include <cmath>
#include <iostream>

constexpr int MAXS = 200000;  // 2sqrt(n)
constexpr int mod = 1000000007;

template <typename x_t, typename y_t>
void inc(x_t &x, const y_t &y) {
  x += y;
  (mod <= x) && (x -= mod);
}

template <typename x_t, typename y_t>
void dec(x_t &x, const y_t &y) {
  x -= y;
  (x < 0) && (x += mod);
}

template <typename x_t, typename y_t>
int sum(const x_t &x, const y_t &y) {
  return x + y < mod ? x + y : (x + y - mod);
}

template <typename x_t, typename y_t>
int sub(const x_t &x, const y_t &y) {
  return x < y ? x - y + mod : (x - y);
}

template <typename _Tp>
int div2(const _Tp &x) {
  return ((x & 1) ? x + mod : x) >> 1;
}

// 以上目的均为防负数和取模
template <typename _Tp>
long long sqrll(const _Tp &x) {  // 平方函数
  return (long long)x * x;
}

int pri[MAXS / 7], lpf[MAXS + 1], spri[MAXS + 1], pcnt;

void sieve(const int &n) {
  for (int i = 2; i <= n; ++i) {
    if (lpf[i] == 0) {  // 记录质数
      lpf[i] = ++pcnt;
      pri[lpf[i]] = i;
      spri[pcnt] = sum(spri[pcnt - 1], i);  // 前缀和
    }
    for (int j = 1, v; j <= lpf[i] && (v = i * pri[j]) <= n; ++j) lpf[v] = j;
  }
}

long long global_n;
int lim;
int le[MAXS + 1],  // x <= \sqrt{n}
    ge[MAXS + 1];  // x > \sqrt{n}
#define idx(v) (v <= lim ? le[v] : ge[global_n / v])

int G[MAXS + 1][2], Fprime[MAXS + 1];
long long lis[MAXS + 1];
int cnt;

void init(const long long &n) {
  for (long long i = 1, j, v; i <= n; i = n / j + 1) {
    j = n / i;
    v = j % mod;
    lis[++cnt] = j;
    (j <= lim ? le[j] : ge[global_n / j]) = cnt;
    G[cnt][0] = sub(v, 1ll);
    G[cnt][1] = div2((long long)(v + 2ll) * (v - 1ll) % mod);
  }
}

void calcFprime() {
  for (int k = 1; k <= pcnt; ++k) {
    const int p = pri[k];
    const long long sqrp = sqrll(p);
    for (int i = 1; lis[i] >= sqrp; ++i) {
      const long long v = lis[i] / p;
      const int id = idx(v);
      dec(G[i][0], sub(G[id][0], k - 1));
      dec(G[i][1], (long long)p * sub(G[id][1], spri[k - 1]) % mod);
    }
  }
  /* F_prime = G_1 - G_0 */
  for (int i = 1; i <= cnt; ++i) Fprime[i] = sub(G[i][1], G[i][0]);
}

int f_p(const int &p, const int &c) {
  /* f(p^{c}) = p xor c */
  return p ^ c;
}

int F(const int &k, const long long &n) {
  if (n < pri[k] || n <= 1) return 0;
  const int id = idx(n);
  long long ans = Fprime[id] - (spri[k - 1] - (k - 1));
  if (k == 1) ans += 2;
  for (int i = k; i <= pcnt && sqrll(pri[i]) <= n; ++i) {
    long long pw = pri[i], pw2 = sqrll(pw);
    for (int c = 1; pw2 <= n; ++c, pw = pw2, pw2 *= pri[i])
      ans +=
          ((long long)f_p(pri[i], c) * F(i + 1, n / pw) + f_p(pri[i], c + 1)) %
          mod;
  }
  return ans % mod;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> global_n;
  lim = sqrt(global_n);  // 上限

  sieve(lim + 1000);  // 预处理
  init(global_n);
  calcFprime();
  cout << (F(1, global_n) + 1ll + mod) % mod << '\n';

  return 0;
}
Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:Marcythm, Xeonacid, CSPNOIP
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply