Chia khối theo thương và tổng floor
Tính các tổng dạng sum f(i) * floor(n/i) trong O(sqrt n) bằng chia khối theo thương (kể cả hai biến và hàm trần), và thuật toán floor_sum kiểu Euclid tính sum floor((a*i+b)/m) trong O(log m) để đếm điểm nguyên dưới đường thẳng.
Rất nhiều công thức số học có dạng : tổng số ước của , tổng các phần dư , số cặp nguyên tố cùng nhau qua hàm Möbius, tổng qua hàm Euler. Tính trực tiếp tốn , quá chậm khi . Chia khối theo thương (division blocking) dựa trên một quan sát đơn giản: chỉ nhận không quá giá trị khác nhau, và các cùng thương tạo thành một đoạn liên tiếp, nên cả tổng chỉ còn khối. Trang này cũng trình bày một công cụ "họ hàng": thuật toán floor_sum tính trong bằng một vòng lặp giống thuật toán Euclid, dùng để đếm điểm nguyên dưới một đường thẳng.
Ý tưởng / Trực giác
Vì sao chỉ có giá trị. Chia các làm hai nhóm:
- : có không quá số , nên không quá giá trị thương.
- : thương , nên cũng chỉ có không quá giá trị.
Tổng cộng không quá giá trị phân biệt.
Vì sao biên phải của khối là . Hàm không tăng, nên các có cùng thương đứng liền nhau. Với :
Vậy là chỉ số lớn nhất còn có thương . Bắt đầu khối tại với , khối kết thúc tại , rồi khối sau bắt đầu ở .
Tổng có trọng số. Trong khối thương là hằng số , nên
Chỉ cần tính nhanh tổng tiền tố của trọng số: thì ; thì ; hoặc thì sàng sẵn mảng tiền tố (xem Hàm nhân tính), còn khi quá lớn để sàng thì dùng các kỹ thuật tính tiền tố hàm nhân tính dưới tuyến tính như ở trang Đếm số nguyên tố, vốn cũng chỉ cần giá trị tại các điểm .
Hai biến. Với tổng chứa đồng thời và , một khối phải giữ nguyên cả hai thương, nên lấy biên phải nhỏ hơn:
Mỗi điểm cắt khối là một điểm cắt của dãy hoặc của dãy , nên số khối không quá .
floor_sum: đếm điểm nguyên theo hai chiều. Với , , đặt
Đây là số điểm nguyên với , và , tức số điểm nguyên nằm dưới đường thẳng (không tính trục hoành). Thuật toán lặp hai bước:
- Tách phần nguyên. Nếu , viết : mỗi số hạng được cộng thêm , tổng là . Tương tự nếu thì cộng . Sau bước này .
- Đếm theo hàng thay vì theo cột. Đặt và (số hàng có điểm). Nếu thì mọi số hạng còn lại bằng , dừng. Ngược lại, ở hàng (), các cột hợp lệ là , nên số điểm là Đổi biến (chạy từ đến ), ta có , do đó
Bài toán mới có mô-đun là và hệ số là : cặp biến thành , rồi ở vòng sau bước 1 rút về . Đó đúng là một bước của thuật toán Euclid, nên số vòng lặp là .
Ví dụ chạy tay
Các khối của .
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 10 | 5 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | 1 |
Mảng dưới đây chạy từng khối, ô chứa giá trị :
array 10 10 5 3 2 2 1 1 1 1 1 step l = 1: q = 10/1 = 10, r = 10/10 = 1 highlight red 1 pointer l 1 pointer r 1 step l = 2: q = 5, r = 10/5 = 2 highlight orange 2 pointer l 2 pointer r 2 step l = 3: q = 3, r = 10/3 = 3 highlight green 3 pointer l 3 pointer r 3 step l = 4: q = 2, r = 10/2 = 5 highlight blue 4..5 pointer l 4 pointer r 5 step l = 6: q = 1, r = 10/1 = 10, xong highlight purple 6..10 pointer l 6 pointer r 10
| khối | |||
|---|---|---|---|
| 10 | 10 | ||
| 5 | 5 | ||
| 3 | 3 | ||
| 2 | |||
| 1 | |||
| tổng | 27 | 87 |
là tổng số ước của (), còn là tổng các tổng ước . Chỉ khối thay vì số hạng; với là khoảng khối thay vì số hạng.
Đếm cặp nguyên tố cùng nhau với . Theo nghịch đảo Möbius, số cặp có là . Với , tiền tố Mertens :
| khối | đóng góp | ||
|---|---|---|---|
| 100 | 100 | ||
| 25 | |||
| 9 | |||
| 4 | |||
| 1 | 1 |
Tổng . Nếu , thì các khối hai biến là (khối của bị cắt tại ), cho đáp án .
floor_sum với , , , . Các số hạng với là , tổng . Bảng dưới vẽ các điểm được đếm (ô #), cột là , hàng trên cùng là :
grid ....# ...## .#### label 1,5 j=3 label 2,5 j=2 label 3,5 j=1
Đếm theo cột: . Đếm theo hàng: hàng có lần lượt điểm, đúng bằng với . Thuật toán chạy như sau:
| vòng | tách | tách | trạng thái mới | ||
|---|---|---|---|---|---|
| 1 | không | không | , , đổi chỗ: | ||
| 2 | , | , | , , đổi chỗ: | ||
| 3 | , | , | , dừng |
Kết quả . Ở vòng 2, : đúng là đếm hàng của hình trên theo thứ tự ngược.
Cài đặt
Duyệt khối một biến. Chương trình đọc , in từng khối l r q, rồi in và (chính xác với ). Với đầu vào 10 nó in đúng năm khối ở bảng trên và dòng cuối 27 87.
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
long long divisorCountSum = 0; // sum_{i=1}^{n} floor(n/i)
long long divisorSigmaSum = 0; // sum_{i=1}^{n} i * floor(n/i), exact for n <= 1e9
for (long long l = 1, r; l <= n; l = r + 1) {
long long q = n / l;
r = n / q; // last i with floor(n/i) == q
cout << l << ' ' << r << ' ' << q << '\n';
divisorCountSum += (r - l + 1) * q;
// sum of i over [l, r] is (l + r) * (r - l + 1) / 2
divisorSigmaSum += (l + r) * (r - l + 1) / 2 * q;
}
cout << divisorCountSum << ' ' << divisorSigmaSum << '\n';
}
import sys
def main():
n = int(sys.stdin.readline())
count_sum = 0 # sum_{i=1}^{n} floor(n/i)
sigma_sum = 0 # sum_{i=1}^{n} i * floor(n/i)
l = 1
while l <= n:
q = n // l
r = n // q # last i with floor(n/i) == q
print(l, r, q)
count_sum += (r - l + 1) * q
sigma_sum += (l + r) * (r - l + 1) // 2 * q
l = r + 1
print(count_sum, sigma_sum)
main()
Khối hai biến: đếm cặp nguyên tố cùng nhau. Đọc truy vấn , sàng tuyến tính, lấy tiền tố rồi chia khối theo cả và . Với đầu vào 4 / 10 10 / 5 5 / 3 7 / 6 6 chương trình in 63, 19, 16, 23.
#include <bits/stdc++.h>
using namespace std;
int main() {
int Q;
cin >> Q;
vector<pair<int, int>> qs(Q);
int maxN = 1;
for (auto& [n, m] : qs) {
cin >> n >> m;
maxN = max(maxN, min(n, m));
}
// Linear sieve for Mobius, then prefix sums M[d] = mu(1) + ... + mu(d)
vector<int> mu(maxN + 1, 0), primes;
vector<bool> composite(maxN + 1, false);
mu[1] = 1;
for (int i = 2; i <= maxN; i++) {
if (!composite[i]) { primes.push_back(i); mu[i] = -1; }
for (int p : primes) {
if ((long long)i * p > maxN) break;
composite[i * p] = true;
if (i % p == 0) { mu[i * p] = 0; break; }
mu[i * p] = -mu[i];
}
}
vector<long long> M(maxN + 1, 0);
for (int d = 1; d <= maxN; d++) M[d] = M[d - 1] + mu[d];
for (auto [n, m] : qs) {
// pairs (i, j), 1 <= i <= n, 1 <= j <= m, gcd = 1
// = sum_d mu(d) * floor(n/d) * floor(m/d), grouped by blocks of (n/d, m/d)
long long ans = 0;
int lim = min(n, m);
for (int l = 1, r; l <= lim; l = r + 1) {
r = min(n / (n / l), m / (m / l)); // both quotients stay constant on [l, r]
ans += (M[r] - M[l - 1]) * (long long)(n / l) * (m / l);
}
cout << ans << '\n';
}
}
import sys
def main():
data = sys.stdin.read().split()
Q = int(data[0])
qs = [(int(data[1 + 2 * k]), int(data[2 + 2 * k])) for k in range(Q)]
max_n = max(1, max(min(n, m) for n, m in qs))
# Linear sieve for Mobius, then prefix sums M[d]
mu = [0] * (max_n + 1)
mu[1] = 1
composite = [False] * (max_n + 1)
primes = []
for i in range(2, max_n + 1):
if not composite[i]:
primes.append(i)
mu[i] = -1
for p in primes:
if i * p > max_n:
break
composite[i * p] = True
if i % p == 0:
mu[i * p] = 0
break
mu[i * p] = -mu[i]
M = [0] * (max_n + 1)
for d in range(1, max_n + 1):
M[d] = M[d - 1] + mu[d]
out = []
for n, m in qs:
ans = 0
lim = min(n, m)
l = 1
while l <= lim:
r = min(n // (n // l), m // (m // l)) # both quotients constant on [l, r]
ans += (M[r] - M[l - 1]) * (n // l) * (m // l)
l = r + 1
out.append(ans)
print("\n".join(map(str, out)))
main()
floor_sum. Đọc bộ và in . Với đầu vào 3 / 5 3 2 1 / 4 10 6 3 / 1000000000 999999937 999999929 999999921 chương trình in 7, 3, 499999995999999705.
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
// sum_{i=0}^{n-1} floor((a*i + b) / m), requires n, m >= 1 and a, b >= 0.
// Euclid-like: reduce a, b below m, then swap the roles of a and m.
// Values are kept below 2^64 as long as n, m, a, b < 2^32 (AtCoder Library style).
ull floor_sum(ull n, ull m, ull a, ull b) {
ull ans = 0;
while (true) {
if (a >= m) { // floor((a i + b)/m) gets (a/m) * i extra
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) { // and (b/m) extra on every term
ans += n * (b / m);
b %= m;
}
ull y_max = a * n + b; // the line value just past the last column
if (y_max < m) break; // every remaining term is 0
// count the same lattice points row by row: n' = y_max/m, b' = y_max%m, swap m and a
n = y_max / m;
b = y_max % m;
swap(m, a);
}
return ans;
}
int main() {
int q;
cin >> q;
while (q--) {
ull n, m, a, b;
cin >> n >> m >> a >> b;
cout << floor_sum(n, m, a, b) << '\n';
}
}
import sys
def floor_sum(n, m, a, b):
"""sum_{i=0}^{n-1} (a*i + b) // m, with n, m >= 1 and a, b >= 0."""
ans = 0
while True:
if a >= m:
ans += n * (n - 1) // 2 * (a // m)
a %= m
if b >= m:
ans += n * (b // m)
b %= m
y_max = a * n + b
if y_max < m:
break
n, b = divmod(y_max, m)
m, a = a, m
return ans
def main():
data = sys.stdin.read().split()
q = int(data[0])
out = []
for k in range(q):
n, m, a, b = map(int, data[1 + 4 * k: 5 + 4 * k])
out.append(floor_sum(n, m, a, b))
print("\n".join(map(str, out)))
main()
Độ phức tạp
| Thao tác | Thời gian | Bộ nhớ |
|---|---|---|
| Duyệt khối , | lần tính tiền tố | |
| Khối hai biến | ||
| Đếm cặp nguyên tố cùng nhau, truy vấn | với | cho sàng |
| floor_sum | sau khi tách |
Vì sao duyệt khối là ? Mỗi vòng lặp xử lý trọn một giá trị thương, và theo lập luận hai nhóm ở trên có không quá giá trị. Nếu tiền tố tính được trong (công thức đóng hoặc mảng sàng sẵn) thì cả tổng là .
Vì sao floor_sum là ? Mỗi vòng biến cặp thành ở vòng sau, giống hệt một bước Euclid, nên số vòng bị chặn bởi số bước Euclid trên , tức . Mỗi vòng phép tính.
⚠️ Lỗi thường gặp
- Chia cho khi chặn trên khác . Nếu tổng chạy với (ví dụ ), thì khi ta có và chia cho . Cách tránh: chỉ chia khối tới , phần có thương xử lý riêng (ở đó ). Với hai biến, dừng ở vì sau đó một trong hai thương bằng .
Nhầm biên khối của hàm trần. Áp nguyên công thức cho là sai: với , thì nhưng , vòng lặp đi lùi hoặc lặp vô hạn. Cách đúng là dùng và chia khối trên , cẩn thận khi (từ đó trở đi thương trần bằng ):
for (long long l = 1, r; l <= n; l = r + 1) { long long k = (n - 1) / l; // ceil(n/l) = k + 1 r = (k == 0) ? n : min(n, (n - 1) / k); // every i in [l, r] has ceil(n/i) == k + 1 }Với các khối là , , , , , .
- Tràn số khi nhân trong khối. thì an toàn (), nhưng với vượt . Lấy modulo trước khi nhân, hoặc dùng
__int128. Với công thức theo modulo, chia trên số nguyên trước khi lấy modulo (một trong , chẵn) chứ không chia sau khi đã lấy modulo. - Nhân với số hạng sai. Trong khối phải dùng , không phải hay . Quên điều này chỉ sai khi khối dài hơn , nên test với nhỏ (khối toàn độ dài ) không phát hiện được; hãy so với brute force ở .
sqrtsố thực lệch. Lời giải kiểu cần chính xác; với gần trở lênsqrtcó thể lệch . Chỉnh lại bằngwhile (k * k > n) k--; while ((k + 1) * (k + 1) <= n) k++;. Duyệt khối với thì không cần căn nên tránh được lỗi này.- floor_sum với đối số âm. Phép
/của C++ cắt về , không làm tròn xuống, và phiên bản không dấu ở trên giả sử . Nếu (hoặc ), chuẩn hoá trước: cộng một bội của vào rồi trừ lại phần đã cộng, ví dụ ; với thay bằng (dương) và bù . - floor_sum tràn 64 bit. Bản
unsigned long longan toàn khi và đáp án vừa 64 bit; khi đầu vào có , đáp án thật có thể lớn hơn và kết quả chỉ đúng theo modulo . Nếu đề yêu cầu modulo , hãy lấy modulo ở các phép cộng phần tách, còn phép biến đổi vẫn giữ số nguyên thật.
Biến thể / Mở rộng
- Số ước và tổng ước của : và . Tổng phần dư quy về cùng dạng.
- Tổng có thương lồng nhau: , nên tập đóng với phép "chia tiếp". Đây là lý do các thuật toán tính tiền tố hàm nhân tính (Mertens, đếm số nguyên tố kiểu Lucy, min25) chỉ cần lưu giá trị tại điểm ; xem Đếm số nguyên tố.
- Möbius và Euler: , , . Nền tảng tích Dirichlet và nghịch đảo Möbius ở Hàm nhân tính; bản chất "cộng trừ theo ước" là bao hàm loại trừ.
- Tối ưu trên khối: khi cần hoặc của biểu thức chứa , giá trị tối ưu thường nằm ở biên các khối, nên chỉ cần thử ứng viên.
- Điểm nguyên dưới đường thẳng và số dư tuyến tính: số có bằng . Tổng . Tổng quát hơn, các tổng , cũng có truy hồi kiểu Euclid ("universal Euclidean"). Khai triển liên phân số của trong thuật toán chính là đường đi trên cây Stern-Brocot.
Bài tập luyện
- Tổng số ước (dhbb25dx4110_tongsouoc): (Trung bình) Tổng số ước của các số trong với : đáp án với , đúng bài mẫu đầu tiên của kỹ thuật.
- Đếm cặp nguyên tố cùng nhau trên lưới (coprgrid): (Trung bình) Đếm cặp nguyên tố cùng nhau qua , luyện khối hai biến với tiền tố Möbius.
- Jzzhu và Thanh Sô Cô La (jzzchoco): (Khó) Tối đa với cố định; nghiệm tối ưu nằm ở biên khối, chỉ thử ứng viên.
- Tổng phần dư (sumrem): (Rất khó) Tính với theo modulo: tổng có trọng số , phải xử lý và tràn số khi nhân.
- Đếm số dư nhỏ (ck10flr): (Rất khó) Đếm với cho truy vấn, quy về hiệu hai lần floor_sum.
- Hàm Mertens (mertens): (Chuyên gia) Tính với qua truy hồi , chia khối theo và ghi nhớ trên tập giá trị .
Bình luận