Chia khối theo giá trị n // i

Mức độ: Chuyên sâu

Rất nhiều công thức số học có dạng tổng f(i) × (n // i) với i từ 1 đến n: tổng số ước, tổng các số dư, số cặp nguyên tố cùng nhau (bài Hàm Möbius). Khi n tới 10¹², cộng từng số hạng là không thể. Nhưng n // i chỉ có rất ít giá trị khác nhau, và đó là chìa khóa của bài này.

Các bạn cần nắm vững bài Hàm Euler và bài Hàm nhân tính và hàm Möbius.

n // i có ít giá trị

Với n = 20:

i	1	2	3	4	5	6	7	8	9	10	11..20
20 // i	20	10	6	5	4	3	2	2	2	2	1

Chỉ có 8 giá trị khác nhau. Lý do, với s = ⌊√n⌋:

Khi i ≤ s, chỉ có s giá trị của i.
Khi i lớn hơn s, n // i nhỏ hơn hoặc bằng s, nên cũng chỉ có tối đa s giá trị.

Vậy n // i có không quá 2√n giá trị khác nhau. Với n = 10¹² là 2 × 10⁶.

Chia khối

Các i có cùng giá trị q = n // i nằm liền nhau thành một khối. Khối bắt đầu ở l thì có q = n // l, và kết thúc ở

r = n // q = n // (n // l)

(số i lớn nhất mà n // i vẫn bằng q). Xử lý cả khối một lần rồi nhảy sang l = r + 1.

Python
C++

def tong_thuong(n):
    """n // 1 + n // 2 + ... + n // n trong khoảng 2√n bước"""
    kq, l = 0, 1
    while l <= n:
        q = n // l
        r = n // q                 # cuối khối có cùng giá trị q
        kq += q * (r - l + 1)
        l = r + 1
    return kq

print(tong_thuong(20))           # 66
print(tong_thuong(10 ** 12))

#include <iostream>
using namespace std;

// n / 1 + n / 2 + ... + n / n trong khoảng 2√n bước
long long tongThuong(long long n) {
    long long kq = 0;
    for (long long l = 1, r; l <= n; l = r + 1) {
        long long q = n / l;
        r = n / q;                 // cuối khối có cùng giá trị q
        kq += q * (r - l + 1);
    }
    return kq;
}

int main() {
    cout << tongThuong(20) << endl;              // 66
    cout << tongThuong(1000000000000LL) << endl;
    return 0;
}

Tổng n // i cũng chính là d(1) + d(2) + … + d(n) (tổng số ước): n // i là số bội của i không quá n, nên mỗi i được đếm một lần cho mỗi số k ≤ n mà i là ước.

Khi số hạng có thêm f(i) (ví dụ tổng i × (n // i)), trong khối chỉ cần tổng f(l) + … + f(r), tính bằng công thức (tổng i, tổng i²) hoặc tổng tiền tố tính sẵn.

Hai biến

Với tổng f(d) × (N // d) × (M // d), cả hai thương cùng không đổi trên khối

r = min(N // (N // l), M // (M // l))

Số khối không quá 2√N + 2√M. Đây là cách trả lời nhanh nhiều câu hỏi kiểu “đếm cặp (x, y) với x ≤ N, y ≤ M có ƯCLN = 1”: tính sẵn tổng tiền tố P của μ, mỗi khối đóng góp (N // l) × (M // l) × (P[r] - P[l - 1]). Mỗi câu hỏi chỉ mất khoảng 4√N bước thay vì N bước.

Mẹo hyperbol

Số cặp (a, b) với a × b ≤ n bằng tổng n // a. Với s = ⌊√n⌋, mọi cặp có a ≤ s hoặc b ≤ s, nên

tổng n // a = 2 × (n // 1 + … + n // s) - s²

(trừ s² cặp có cả hai thành phần ≤ s, bị đếm hai lần). Cách này cũng cần √n bước nhưng đơn giản hơn chia khối.

Tổng φ và tổng μ đến 10⁹

Để tính S(n) = φ(1) + … + φ(n) với n = 10⁹, không sàng được. Dùng đẳng thức k = tổng φ(d) trên các ước d của k, cộng với k từ 1 đến n rồi gom theo i = k / d:

n(n + 1) / 2 = tổng S(n // i) với i từ 1 đến n

S(n) = n(n + 1) / 2 - tổng S(n // i) với i từ 2 đến n.

Tổng bên phải chia khối theo n // i, và mọi giá trị S cần đến đều có dạng S(n // k), nên nhớ lại kết quả đã tính. Sàng sẵn S cho các số đến L ≈ n^2/3 (với n = 10⁹ là 10⁶), tổng số bước cỡ n^2/3. Kỹ thuật này thường được gọi là sàng Đỗ Giáo.

Python
C++

def sang_phi(N):
    ph = list(range(N + 1))
    for i in range(2, N + 1):
        if ph[i] == i:
            for j in range(i, N + 1, i):
                ph[j] -= ph[j] // i
    return ph

L = 1000000
ph = sang_phi(L)
S_NHO = [0] * (L + 1)
for i in range(1, L + 1):
    S_NHO[i] = S_NHO[i - 1] + ph[i]
nho = {}

def tong_phi(x):
    if x <= L:
        return S_NHO[x]
    if x in nho:
        return nho[x]
    kq, l = x * (x + 1) // 2, 2
    while l <= x:
        q = x // l
        r = x // q
        kq -= (r - l + 1) * tong_phi(q)
        l = r + 1
    nho[x] = kq
    return kq

print(tong_phi(10 ** 9))

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

const int L = 1000000;
vector<long long> sNho;
unordered_map<long long, long long> nhoLon;

long long tongPhi(long long x) {
    if (x <= L) return sNho[x];
    auto it = nhoLon.find(x);
    if (it != nhoLon.end()) return it->second;
    long long kq = x * (x + 1) / 2;
    for (long long l = 2, r; l <= x; l = r + 1) {
        long long q = x / l;
        r = x / q;
        kq -= (r - l + 1) * tongPhi(q);
    }
    nhoLon[x] = kq;
    return kq;
}

int main() {
    vector<int> ph(L + 1);
    for (int i = 0; i <= L; i++) ph[i] = i;
    for (int i = 2; i <= L; i++)
        if (ph[i] == i)
            for (int j = i; j <= L; j += i) ph[j] -= ph[j] / i;
    sNho.assign(L + 1, 0);
    for (int i = 1; i <= L; i++) sNho[i] = sNho[i - 1] + ph[i];
    cout << tongPhi(1000000000) << endl;
    return 0;
}

Với μ làm tương tự, dùng đẳng thức tổng μ(d) trên các ước d của k bằng 1 khi k = 1 và bằng 0 khi k lớn hơn 1: M(n) = 1 - tổng M(n // i) với i từ 2 đến n.

Lưu ý: bí quyết chung là đổi thứ tự cộng. Tổng theo i rồi theo bội của i, đổi thành tổng theo k rồi theo ước của k, sẽ biến những tổng khó thành những đẳng thức đơn giản (tổng φ trên ước bằng k, tổng μ trên ước bằng 0 hoặc 1).

Luyện tập

Gồm 20 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Tổng với n // i

Bài 1. Tổng n // i

Nhập n (1 ≤ n ≤ 10¹²). In ra n // 1 + n // 2 + … + n // n.

Ví dụ: nhập 10 thì in ra 27.

Kiểm tra: nhập 1000000000000.

Xem đáp số

27785452449086

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Tổng i × (n // i)

Nhập n (1 ≤ n ≤ 10¹²). In ra tổng i × (n // i) với i từ 1 đến n, lấy dư cho 10⁹ + 7.

Ví dụ: nhập 10 thì in ra 87.

Kiểm tra: nhập 1000000000000.

Xem đáp số

146462362

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Tổng các số dư

Nhập n (1 ≤ n ≤ 10¹²). In ra (n mod 1) + (n mod 2) + … + (n mod n), lấy dư cho 10⁹ + 7.

Ví dụ: nhập 10 thì in ra 13.

Kiểm tra: nhập 1000000000000.

Xem đáp số

902537645

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Có bao nhiêu giá trị khác nhau

Nhập n (1 ≤ n ≤ 10¹⁸). In ra số giá trị khác nhau của n // i với i từ 1 đến n.

Ví dụ: nhập 10 thì in ra 5.

Kiểm tra: nhập 1000000000000000000.

Xem đáp số

1999999999

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Tổng k mod i

Nhập n và k (1 ≤ n, k ≤ 10⁹). In ra (k mod 1) + (k mod 2) + … + (k mod n).

Ví dụ: nhập 5 3 thì in ra 7.

Kiểm tra: nhập 1000000000 987654321.

Xem đáp số

185369758011162322

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Hai biến và nhiều câu hỏi

Bài 6. Tích hai thương

Nhập n, m (1 ≤ n, m ≤ 10¹²). In ra tổng (n // i) × (m // i) với i từ 1 đến min(n, m), lấy dư cho 10⁹ + 7.

Ví dụ: nhập 10 6 thì in ra 86.

Kiểm tra: nhập 1000000000000 999999999999.

Xem đáp số

145865462

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Nhiều câu hỏi đếm cặp nguyên tố cùng nhau

Dòng đầu là Q (Q ≤ 1000). Q dòng sau mỗi dòng có N, M (1 ≤ N, M ≤ 10⁶). Với mỗi dòng in ra số cặp (x, y), 1 ≤ x ≤ N, 1 ≤ y ≤ M, có ƯCLN(x, y) = 1.

Ví dụ:

Nhập	In ra
`2` `3 4` `10 10`	`9` `63`

Kiểm tra: nhập

3
1000000 1000000
1000000 1
999999 123456

Xem đáp số

607927104783
1000000
75052295136

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Nhiều câu hỏi: ƯCLN là số nguyên tố

Dòng đầu là Q (Q ≤ 1000). Q dòng sau mỗi dòng có N, M (1 ≤ N, M ≤ 10⁶). Với mỗi dòng in ra số cặp (x, y), 1 ≤ x ≤ N, 1 ≤ y ≤ M, có ƯCLN(x, y) là số nguyên tố.

Ví dụ:

Nhập	In ra
`2` `4 4` `10 10`	`4` `30`

Kiểm tra: nhập

3
1000000 1000000
1000000 7
999999 123456

Xem đáp số

274934018418
1926191
33942347144

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Nhiều câu hỏi tổng ƯCLN

Dòng đầu là Q (Q ≤ 1000). Q dòng sau mỗi dòng có N, M (1 ≤ N, M ≤ 10⁶). Với mỗi dòng in ra tổng ƯCLN(x, y) với 1 ≤ x ≤ N, 1 ≤ y ≤ M.

Ví dụ:

Nhập	In ra
`2` `3 4` `3 3`	`16` `12`

Kiểm tra: nhập

3
1000000 1000000
1000000 1
999999 123456

Xem đáp số

8643257847824
1000000
930502672160

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Bộ ba có tích không quá n

Nhập n (1 ≤ n ≤ 10⁸). In ra số bộ ba có thứ tự (a, b, c) các số nguyên dương với a × b × c ≤ n.

Ví dụ: nhập 4 thì in ra 13.

Kiểm tra: nhập 100000000.

Xem đáp số

18362473634

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Tổng hàm nhân tính với n rất lớn

Bài 11. Tổng φ đến 10^9

Nhập n (1 ≤ n ≤ 10⁹). In ra φ(1) + φ(2) + … + φ(n).

Ví dụ: nhập 10 thì in ra 32.

Kiểm tra: nhập 1000000000.

Xem đáp số

303963551173008414

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Tổng μ đến 10^9

Nhập n (1 ≤ n ≤ 10⁹). In ra μ(1) + μ(2) + … + μ(n).

Ví dụ: nhập 10 thì in ra -1.

Kiểm tra: nhập 1000000000.

Xem đáp số

-222

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Cặp nguyên tố cùng nhau đến 10^9

Nhập n (1 ≤ n ≤ 10⁹). In ra số cặp có thứ tự (x, y) với 1 ≤ x, y ≤ n và ƯCLN(x, y) = 1.

Ví dụ: nhập 3 thì in ra 7.

Kiểm tra: nhập 1000000000.

Xem đáp số

607927102346016827

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Tổng ƯCLN mọi cặp đến 10^9

Nhập n (1 ≤ n ≤ 10⁹). In ra tổng ƯCLN(x, y) với mọi 1 ≤ x, y ≤ n, lấy dư cho 10⁹ + 7.

Ví dụ: nhập 3 thì in ra 12.

Kiểm tra: nhập 1000000000.

Xem đáp số

235795080

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Vận dụng

Bài 15. Tổng (n // i) × i bình phương

Nhập n (1 ≤ n ≤ 10¹²). In ra tổng (n // i) × i² với i từ 1 đến n, lấy dư cho 10⁹ + 7.

Ví dụ: nhập 4 thì in ra 37.

Kiểm tra: nhập 1000000000000.

Xem đáp số

549367914

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Tổng n // i trên một đoạn

Nhập n, a, b (1 ≤ a ≤ b ≤ n ≤ 10¹²). In ra tổng n // i với i từ a đến b.

Ví dụ: nhập 10 3 7 thì in ra 9.

Kiểm tra: nhập 1000000000000 123456789 987654321098.

Xem đáp số

8564551067120

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Tổng các giá trị khác nhau

Nhập n (1 ≤ n ≤ 10¹²). In ra tổng các giá trị khác nhau của n // i với i từ 1 đến n.

Ví dụ: nhập 10 thì in ra 21.

Kiểm tra: nhập 1000000000000.

Xem đáp số

14892725724543

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Tổng n // i bình phương

Nhập n (1 ≤ n ≤ 10¹⁴). In ra tổng n // i² với mọi i nguyên dương có i² ≤ n.

Ví dụ: nhập 10 thì in ra 13.

Kiểm tra: nhập 100000000000000.

Xem đáp số

164493392081212

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Cặp có tích không quá n

Nhập n (1 ≤ n ≤ 10¹⁴). In ra số cặp (a, b) các số nguyên dương với a ≤ b và a × b ≤ n.

Ví dụ: nhập 6 thì in ra 8.

Kiểm tra: nhập 100000000000000.

Xem đáp số

1619531136590527

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Một tổng bất ngờ

Nhập n (1 ≤ n ≤ 10¹⁸). In ra tổng φ(i) × (n // i) với i từ 1 đến n, lấy dư cho 10⁹ + 7.

Ví dụ: nhập 4 thì in ra 10.

Kiểm tra: nhập 1000000000000000000.

Xem đáp số

1225

Hướng dẫn giải chi tiết: liên hệ tác giả.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English

Chia khối theo giá trị n // i

n // i có ít giá trị

Chia khối

Hai biến

Mẹo hyperbol

Tổng φ và tổng μ đến 109

Luyện tập

Nhóm 1. Tổng với n // i

Bài 1. Tổng n // i

Bài 2. Tổng i × (n // i)

Bài 3. Tổng các số dư

Bài 4. Có bao nhiêu giá trị khác nhau

Bài 5. Tổng k mod i

Nhóm 2. Hai biến và nhiều câu hỏi

Bài 6. Tích hai thương

Bài 7. Nhiều câu hỏi đếm cặp nguyên tố cùng nhau

Bài 8. Nhiều câu hỏi: ƯCLN là số nguyên tố

Bài 9. Nhiều câu hỏi tổng ƯCLN

Bài 10. Bộ ba có tích không quá n

Nhóm 3. Tổng hàm nhân tính với n rất lớn

Bài 11. Tổng φ đến 10^9

Bài 12. Tổng μ đến 10^9

Bài 13. Cặp nguyên tố cùng nhau đến 10^9

Bài 14. Tổng ƯCLN mọi cặp đến 10^9

Nhóm 4. Vận dụng

Bài 15. Tổng (n // i) × i bình phương

Bài 16. Tổng n // i trên một đoạn

Bài 17. Tổng các giá trị khác nhau

Bài 18. Tổng n // i bình phương

Bài 19. Cặp có tích không quá n

Bài 20. Một tổng bất ngờ

Tổng φ và tổng μ đến 10⁹