Möbius Function

Hàm Möbius và sàng tuyến tính

$\mu(1) = 1$; $\mu(n) = 0$ nếu $n$ chia hết cho bình phương một số nguyên tố; ngược lại $\mu(n) = (-1)^k$ với $k$ là số thừa số nguyên tố. Với $n > 1$ có $k \ge 1$ thừa số nguyên tố phân biệt, các ước không chứa bình phương của nó là các tập con của $k$ thừa số, nên $\sum_{d \mid n} \mu(d) = \sum_j \binom{k}{j} (-1)^j = 0$. Đây là toàn bộ bí mật: biểu thức $[\gcd = 1]$ thay được bằng $\sum_{d \mid \gcd} \mu(d)$, rồi đổi thứ tự tổng.

Sàng tuyến tính tính $\mu$ cho mọi số tới $N$ trong $O(N)$: mỗi hợp số bị đánh dấu đúng một lần bởi thừa số nguyên tố nhỏ nhất. Khi xét $i$ và số nguyên tố $p \le$ ước nguyên tố nhỏ nhất của $i$: nếu $p \mid i$ thì $\mu(ip) = 0$ và dừng; ngược lại $\mu(ip) = -\mu(i)$.

Ví dụ đầu: số không chứa bình phương tới $N$ là $\sum_{d} \mu(d) \lfloor N / d^2 \rfloor$, với $d$ chạy tới $\sqrt N$: mỗi số $x$ được đếm với trọng số $\sum_{d^2 \mid x} \mu(d)$, bằng 1 đúng khi $x$ không chia hết cho bình phương nào.

Ví dụĐếm Số Không Chứa Bình Phương

Đề. $T \le 100$ truy vấn, mỗi truy vấn $N \le 10^{14}$. Đếm số không chứa bình phương trong $[1, N]$.

Lời giải. Số không chứa bình phương tới $N$ là $\sum_{d \le \sqrt N} \mu(d) \lfloor N / d^2 \rfloor$, nên cần $\mu$ tới $\sqrt{10^{14}} = 10^7$. Duyệt $10^7$ số hạng cho mỗi truy vấn là $10^9$ phép với 100 truy vấn, quá chậm. Nhưng thương $q = \lfloor N/d^2 \rfloor$ chỉ có $O(N^{1/3})$ giá trị khác nhau, và mọi $d$ từ $d$ tới $e = \lfloor \sqrt{N/q} \rfloor$ cho cùng $q$: gom cả khối, cộng $q \cdot \sum_{d'=d}^{e} \mu(d')$ lấy từ tổng tiền tố.

Bước 1: sàng tuyến tính $\mu$. Mỗi hợp số $i \cdot p$ được đánh dấu đúng một lần, bởi $p$ là ước nguyên tố nhỏ nhất của nó. Khi i % p == 0 thì $p^2 \mid ip$, $\mu = 0$, và dừng: các số nguyên tố lớn hơn không còn là ước nhỏ nhất của $i \cdot p'$. Ngược lại $ip$ có thêm một thừa số nguyên tố mới, $\mu(ip) = -\mu(i)$. mu lưu bằng signed char, pre bằng int, để hai mảng $10^7$ phần tử chỉ tốn khoảng 50 MB.

for (int i = 2; i < M; i++) {
    if (!comp[i]) primes.push_back(i), mu[i] = -1;
    for (int p : primes) {
        if ((ll)i * p >= M) break;
        comp[i * p] = 1;
        if (i % p == 0) {
            mu[i * p] = 0;
            break;
        }
        mu[i * p] = -mu[i];
    }
}

Bước 2: chia khối theo thương. e = isqrt(n / q) là $d$ lớn nhất còn cho $\lfloor N / d^2 \rfloor = q$. isqrt là căn nguyên chính xác như bài 66, vì sqrtl có thể lệch 1 ở gần số chính phương.

for (ll d = 1; d <= lim;) {
    ll q = n / (d * d), e = isqrt(n / q);
    ans += q * (pre[e] - pre[d - 1]);
    d = e + 1;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int M = 1e7 + 5;
int pre[M];
signed char mu[M];
vector<int> primes;
bool comp[M];

ll isqrt(ll x) {
    ll r = sqrtl((long double)x);
    while (r * r > x) r--;
    while ((r + 1) * (r + 1) <= x) r++;
    return r;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    mu[1] = 1;
    for (int i = 2; i < M; i++) {
        if (!comp[i]) primes.push_back(i), mu[i] = -1;
        for (int p : primes) {
            if ((ll)i * p >= M) break;
            comp[i * p] = 1;
            if (i % p == 0) {
                mu[i * p] = 0;
                break;
            }
            mu[i * p] = -mu[i];
        }
    }
    for (int i = 1; i < M; i++) pre[i] = pre[i - 1] + mu[i];
    int T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        ll lim = isqrt(n), ans = 0;
        for (ll d = 1; d <= lim;) {
            ll q = n / (d * d), e = isqrt(n / q);
            ans += q * (pre[e] - pre[d - 1]);
            d = e + 1;
        }
        cout << ans << '\n';
    }
}

Input4
1
10
30
100

Output1
7
19
61

Sàng $O(\sqrt{N})$ một lần; mỗi truy vấn $O(N^{1/3})$ khối, khoảng vài chục nghìn với $N = 10^{14}$.

Đếm theo bội

Gọi $c_d$ là số phần tử của dãy chia hết cho $d$ (tính bằng cách duyệt bội: với mỗi $d$, cộng số lần xuất hiện của $d, 2d, 3d, \dots$, tổng $O(V \log V)$). Số cặp có gcd chia hết cho $d$ là $\binom{c_d}{2}$, số tập con khác rỗng là $2^{c_d} - 1$. Thay $[\gcd = 1] = \sum_{d \mid \gcd} \mu(d)$:

Cùng khuôn mẫu cho bộ ba, bộ bốn ($\binom{c_d}{4}$), dãy có thứ tự trong hộp ($\lfloor n/d \rfloor^k$), điểm nhìn thấy trên lưới.

Ví dụNhững Cặp Không Chung Ước

Đề. Dãy $n \le 10^5$ số tới $10^6$. Đếm cặp chỉ số có hai giá trị nguyên tố cùng nhau.

Lời giải. Số cặp chỉ số có gcd chia hết cho $d$ là $\binom{c_d}{2}$, với $c_d$ là số phần tử chia hết cho $d$. Thay điều kiện $[\gcd = 1]$ bằng $\sum_{d \mid \gcd} \mu(d)$ rồi đổi thứ tự tổng: số cặp nguyên tố cùng nhau là $\sum_d \mu(d) \binom{c_d}{2}$. Sàng tuyến tính $\mu$ tới $10^6$ như ví dụ trước.

Bước 1: $c_d$ qua tần suất. freq[x] là số lần giá trị $x$ xuất hiện; c cộng freq ở $d, 2d, 3d, \dots$. Bỏ qua $d$ có $\mu(d) = 0$, đỡ khoảng 40% số vòng. c * (c - 1) / 2 tới $5 \cdot 10^9$, phải là long long.

for (int d = 1; d < V; d++) {
    if (!mu[d]) continue;
    ll c = 0;
    for (int k = d; k < V; k += d) c += freq[k];
    ans += mu[d] * c * (c - 1) / 2;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int V = 1e6 + 5;
int n, mu[V], freq[V];
bool comp[V];
vector<int> primes;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    mu[1] = 1;
    for (int i = 2; i < V; i++) {
        if (!comp[i]) primes.push_back(i), mu[i] = -1;
        for (int p : primes) {
            if ((ll)i * p >= V) break;
            comp[i * p] = 1;
            if (i % p == 0) {
                mu[i * p] = 0;
                break;
            }
            mu[i * p] = -mu[i];
        }
    }
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        freq[x]++;
    }
    ll ans = 0;
    for (int d = 1; d < V; d++) {
        if (!mu[d]) continue;
        ll c = 0;
        for (int k = d; k < V; k += d) c += freq[k];
        ans += mu[d] * c * (c - 1) / 2;
    }
    cout << ans << '\n';
}

Input6
2 3 4 9 10 25

Output10

$V (1 + \frac12 + \frac13 + \dots) = O(V \log V)$.

Ví dụTập Con Có GCD Bằng Một

Đề. Dãy $n \le 10^5$ số tới $10^5$. Đếm tập chỉ số khác rỗng có gcd bằng 1, theo mô-đun $10^9 + 7$.

Lời giải. Cùng khuôn với ví dụ trước: số tập chỉ số khác rỗng mà mọi phần tử chia hết cho $d$ là $2^{c_d} - 1$, nên đáp án là $\sum_d \mu(d)(2^{c_d} - 1)$ theo mô-đun. $c_d \le n$ nên lũy thừa của 2 tính sẵn tới $n$.

pw[0] = 1;
for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * 2 % MOD;

Số hạng có thể âm khi $\mu(d) = -1$, nên cộng thêm MOD trước khi lấy dư.

ans = (ans + mu[d] * (pw[c] - 1) + MOD) % MOD;

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int V = 1e5 + 5;
const ll MOD = 1e9 + 7;
int n, mu[V], freq[V];
ll pw[V];
bool comp[V];
vector<int> primes;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    mu[1] = 1;
    for (int i = 2; i < V; i++) {
        if (!comp[i]) primes.push_back(i), mu[i] = -1;
        for (int p : primes) {
            if ((ll)i * p >= V) break;
            comp[i * p] = 1;
            if (i % p == 0) {
                mu[i * p] = 0;
                break;
            }
            mu[i * p] = -mu[i];
        }
    }
    cin >> n;
    pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * 2 % MOD;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        freq[x]++;
    }
    ll ans = 0;
    for (int d = 1; d < V; d++) {
        if (!mu[d]) continue;
        int c = 0;
        for (int k = d; k < V; k += d) c += freq[k];
        ans = (ans + mu[d] * (pw[c] - 1) + MOD) % MOD;
    }
    cout << ans << '\n';
}

Input3
2 3 4

Output3

$O(V \log V)$.

Gcd đúng bằng g: trừ từ trên xuống

Đảo Möbius cũng có dạng trừ dần: gọi $F(g)$ là số đối tượng có gcd chia hết cho $g$ (dễ tính), $E(g)$ là số có gcd đúng bằng $g$. Vì $F(g) = \sum_{k \ge 1} E(kg)$, duyệt $g$ từ lớn xuống nhỏ:

Tổng $\sum_g \sum_k$ là $O(K \log K)$, không cần đến $\mu$. Cách này hợp khi cần $E(g)$ cho mọi $g$, như tính tổng gcd: $\sum_g g \cdot E(g)$.

Ví dụTổng GCD Của Mọi Dãy

Đề. Mọi dãy dài $N \le 10^5$ với phần tử trong $[1, K]$, $K \le 10^5$. Tính tổng gcd của chúng theo mô-đun $10^9 + 7$.

Lời giải. Gọi $F(g)$ là số dãy có gcd chia hết cho $g$: mọi phần tử là bội của $g$, mỗi phần tử có $\lfloor K/g \rfloor$ lựa chọn, nên $F(g) = \lfloor K/g \rfloor^N$. $E(g)$ là số dãy có gcd đúng bằng $g$. Vì $F(g) = \sum_{k \ge 1} E(kg)$, duyệt $g$ từ $K$ xuống 1 thì $E(g) = F(g) - \sum_{k \ge 2} E(kg)$, với mọi $E(kg)$ đã tính xong. Đáp án là $\sum_g g \cdot E(g)$.

for (ll g = k; g >= 1; g--) {
    E[g] = power(k / g, n);
    for (ll m = 2 * g; m <= k; m += g) E[g] = (E[g] - E[m] + MOD) % MOD;
    ans = (ans + g * E[g]) % MOD;
}

Kiểm với mẫu: $N = 2$, $K = 3$ có 9 dãy; $E(3) = 1$, $E(2) = 1$, $E(1) = 9 - 1 - 1 = 7$, tổng $7 + 2 + 3 = 12$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;
ll n, k, E[100005];

ll power(ll a, ll b) {
    ll r = 1;
    a %= MOD;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    ll ans = 0;
    for (ll g = k; g >= 1; g--) {
        E[g] = power(k / g, n);
        for (ll m = 2 * g; m <= k; m += g) E[g] = (E[g] - E[m] + MOD) % MOD;
        ans = (ans + g * E[g]) % MOD;
    }
    cout << ans << '\n';
}

Input2 3

Output12

Vòng trừ bội $O(K \log K)$, lũy thừa $O(K \log N)$.

Chia khối theo thương

Số cặp $x \le n$, $y \le m$ có $\gcd(x, y) = 1$ là $\sum_{d \ge 1} \mu(d) \lfloor n/d \rfloor \lfloor m/d \rfloor$. Với nhiều truy vấn, $O(n)$ mỗi truy vấn là quá chậm, nhưng $\lfloor n/d \rfloor$ chỉ có $O(\sqrt n)$ giá trị: với $d$ hiện tại, mọi $d'$ tới $e = \min(n / \lfloor n/d \rfloor, m / \lfloor m/d \rfloor)$ cho cùng cặp thương, nên cộng cả khối bằng tổng tiền tố của $\mu$ trên $[d, e]$. Mỗi truy vấn $O(\sqrt n + \sqrt m)$.

Gcd đúng bằng $k$ trong hình chữ nhật $[1, n] \times [1, m]$: chia hai cạnh cho $k$ rồi đếm cặp nguyên tố cùng nhau. Đoạn $[a, b] \times [c, d]$ thì bao hàm loại trừ bốn góc.

Ví dụTruy Vấn Ước Chung Trên Hai Đoạn

Đề. $T \le 5 \cdot 10^4$ truy vấn $a, b, c, d, k$ (tới $5 \cdot 10^4$). Đếm cặp $x \in [a, b]$, $y \in [c, d]$ có $\gcd(x, y) = k$.

Lời giải. $\gcd(x, y) = k$ khi và chỉ khi $x = k x'$, $y = k y'$ với $\gcd(x', y') = 1$. Vậy số cặp trong $[1, n] \times [1, m]$ là $f(\lfloor n/k \rfloor, \lfloor m/k \rfloor)$, với $f(n, m) = \sum_d \mu(d) \lfloor n/d \rfloor \lfloor m/d \rfloor$ đếm cặp nguyên tố cùng nhau. Đoạn $[a, b] \times [c, d]$ lấy bằng bao hàm loại trừ bốn góc.

Bước 1: $f$ bằng chia khối. Đổi chỗ để $n \le m$, vì khi $d > n$ thì $\lfloor n/d \rfloor = 0$. e là $d$ lớn nhất mà cả hai thương không đổi; cả khối cộng một lần bằng pre[e] - pre[d - 1].

ll f(ll n, ll m) {
    if (n > m) swap(n, m);
    ll res = 0;
    for (ll d = 1; d <= n;) {
        ll e = min(n / (n / d), m / (m / d));
        res += (ll)(pre[e] - pre[d - 1]) * (n / d) * (m / d);
        d = e + 1;
    }
    return res;
}

Bước 2: bốn góc. (a - 1) / k với $a = 1$ bằng 0, và f(0, ·) = 0 vì vòng không chạy.

ll ans = f(b / k, d / k) - f((a - 1) / k, d / k) - f(b / k, (c - 1) / k) + f((a - 1) / k, (c - 1) / k);

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int V = 5e4 + 5;
int mu[V], pre[V];
bool comp[V];
vector<int> primes;

ll f(ll n, ll m) {
    if (n > m) swap(n, m);
    ll res = 0;
    for (ll d = 1; d <= n;) {
        ll e = min(n / (n / d), m / (m / d));
        res += (ll)(pre[e] - pre[d - 1]) * (n / d) * (m / d);
        d = e + 1;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    mu[1] = 1;
    for (int i = 2; i < V; i++) {
        if (!comp[i]) primes.push_back(i), mu[i] = -1;
        for (int p : primes) {
            if ((ll)i * p >= V) break;
            comp[i * p] = 1;
            if (i % p == 0) {
                mu[i * p] = 0;
                break;
            }
            mu[i * p] = -mu[i];
        }
    }
    for (int i = 1; i < V; i++) pre[i] = pre[i - 1] + mu[i];
    int T;
    cin >> T;
    while (T--) {
        ll a, b, c, d, k;
        cin >> a >> b >> c >> d >> k;
        ll ans = f(b / k, d / k) - f((a - 1) / k, d / k) - f(b / k, (c - 1) / k) + f((a - 1) / k, (c - 1) / k);
        cout << ans << '\n';
    }
}

Input3
2 4 3 5 1
2 4 3 5 2
4 6 6 8 2

Output6
1
2

Mỗi truy vấn bốn lần f với khoảng $2\sqrt{5 \cdot 10^4} \approx 450$ khối, tổng khoảng $10^8$ phép nhẹ.