Tác giả: RR
Trong bài viết này, mình sẽ giới thiệu về hàm nhân tính cũng như ứng dụng của nó trong Competitive Programming (lập trình thi đấu).
Một hàm , được coi là hàm nhân tính (Multiplicative Function) nếu:
Với mọi cặp số nguyên tố cùng nhau , ta có .
Ví dụ
Xét hàm là số ước của . Ta có:
f(1) = 1
f(2) = 2
f(3) = 2
f(4) = 3
f(5) = 2
f(6) = 4 = f(2) * f(3)
f(7) = 2
f(8) = 4
f(9) = 3
f(10) = 4 = f(2) * f(5)
f(12) = 6 = f(3) * f(4)
f(18) = 6 = f(2) * f(9)
Ta có thể chứng minh hàm là hàm nhân tính như sau:
Như vậy, .
Giờ ta xét bài toán sau:
Cho số N không quá 10^5. Tính tất cả các f(i) với i <= N.
Để làm những bài dạng này, ta sẽ có 3 bước:
Nếu bạn chưa biết sàng có thể đọc ở đây.
Như đã chứng minh ở phần trước, là hàm nhân tính.
Với một số nguyên tố , ta có , do các ước của là .
Đầu tiên, ta dùng sàng để:
Như vậy, ta có thể cài đặt như sau:
const int MN = 1e6 + 11;
int sieve[MN]; // Sàng số nguyên tố. Sau khi sàng:
// - sieve[i] = 0 nếu i là số nguyên tố
// - ngược lại sieve[i] = một ước bất kỳ của i.
pair<int,int> pk[MN]; // Nếu i có dạng p^k, pk[i] = {p, k}.
// Ngược lại, pk[i] = {-1, 0}
int ndiv[MN]; // ndiv[i] = Số ước của i.
int main() {
// Sàng số nguyên tố
for (int i = 2; i <= 1000; i++) // số không nguyên tố có 1 ước <= 10^3.
if (!sieve[i]) {
for (int j = i*i; j <= 1000000; j += i)
sieve[j] = i;
}
ndiv[1] = 1;
for (int i = 2; i <= 1000000; i++) {
if (!sieve[i]) {
// i là số nguyên tố.
pk[i] = make_pair(i, 1);
ndiv[i] = 2;
}
else {
int p = sieve[i]; // p là ước bất kỳ của i.
if (pk[i/p].first == p) { // i = p^k
pk[i] = make_pair(p, pk[i/p].second + 1);
ndiv[i] = pk[i].second + 1; // ndiv[p^k] = k+1.
}
else {
pk[i] = make_pair(-1, 0);
// Phân tích i = u*v, với gcd(u, v) = 1.
int u = i, v = 1;
while (u % p == 0) {
u /= p;
v = v * p;
}
ndiv[i] = ndiv[u] * ndiv[v];
}
}
}
}
Ta xét bài toán sau:
Cho số N không quá . Tính
Chú ý ở bài toán trước ta cần tính nhiều giá trị của với nhỏ, còn trong bài này ta chỉ cần tính duy nhất 1 giá trị của với lớn.
Cũng như trên, ta sẽ làm theo 3 bước chính:
Vì 2 bước đầu giống hệt phần trước nên mình sẽ không nhắc lại.
Ở bước 3, bạn chỉ cần xét tất cả các số từ 1 đến , từ đó phân tích được thành thừa số nguyên tố. Code như sau:
int n;
int res = 1; // kết quả
for (int i = 2; i*i <= n; i++) {
if (n % i == 0) {
// i là ước nguyên tố của n
// (nếu i không nguyên tố, và có ước p, thì ở bước trước đó,
// ta đã chia n cho p đến khi n không chia hết cho p).
int u = 1, k = 0;
// u = i^k là luỹ thừa lớn nhất của i mà là ước của n.
while (n % i == 0) {
n /= i;
u = u * i;
k += 1;
}
res = res * (k + 1);
}
}
if (n > 1) { // giá trị hiện tại của n là số nguyên tố
res = res * 2;
}
Việc chứng minh trực tiếp một hàm là hàm nhân tính như ví dụ về hàm số ước ở trên không hề đơn giản. Chẳng hạn, bạn hãy thử chứng minh hàm là hàm nhân tính với là tổng các ước của số . Dĩ nhiên bạn có thể chứng minh trâu bò bằng cách viết ra một đống công thức, tuy nhiên ở mục này mình sẽ hướng dẫn các bạn một phương pháp kỳ diệu hơn.
Với 2 hàm và là hàm nhân tính, ta có một hàm nhân tính mới (gọi là Tích chập Dirichlet (Dirichlet Convolution) giữa và ):
Một cách biểu diễn khác là:
Các bạn chú ý kí hiệu nghĩa là chia hết cho .
Chứng minh
Xét và nguyên tố cùng nhau. Mỗi ước của có thể phân tích duy nhất dưới dạng trong đó và , do .
Do đó:
Như vậy, cũng là hàm nhân tính.
Để hiểu thêm về Tích chập Dirichlet, ta xét vài ví dụ:
Xét hàm và . Rõ ràng và đều là hàm nhân tính.
Như vậy là số ước của số và là hàm nhân tính.
Xét hàm và . Rõ ràng và đều là hàm nhân tính.
Như vậy là tổng các ước của và là hàm nhân tính.
Tổng quát hơn, với hằng số bất kỳ, hàm là hàm nhân tính.
Sau đây là các hàm nhân tính thường gặp. Bạn có thể thử chứng minh những hàm này là hàm nhân tính dựa theo định nghĩa hoặc Tích chập Dirichlet. Việc nắm được những hàm này sẽ giúp thuận lợi hơn trong việc gỉai những bài liên quan đến hàm nhân tính.
Như vậy, nếu bạn chứng minh được một hàm là hàm nhân tính, và tìm được công thức cho thì sẽ dễ dàng tính được tất cả các giá trị trong .
Bạn cũng nên nắm được những hàm nhân tính thường gặp, từ đó giúp nhận dạng bài toán dễ dàng hơn.
Gợi ý: Xét .
Gợi ý: Tìm cách bỏ phép cộng trong công thức của .