Nguồn: Quora
Trong bài viết này mình sẽ giới thiệu với các bạn một chủ đề vô cùng thú vị trong số học - Hàm nghịch đảo Mobius, cũng như cách ứng dụng để giải quyết một số bài toán.
Một lời khuyên dành cho bạn đọc là các bạn nên tự chứng minh những công thức được đề cập để hiểu rõ hơn bản chất bài toán.
Trước khi bắt đầu, các bạn hãy ghi nhớ một số định nghĩa sau đây để việc tiếp thu những kiến thức ở dưới được dễ dàng hơn.
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ó
Một số phân tích ra thừa số nguyên tố sẽ có dạng , với là ước nguyên tố của .
Ký hiệu có nghĩa là là ước của , hay chia hết cho
Hàm định danh Dirichlet (Dirichlet identity function):
với
với
với mọi
với mọi
Hàm Mobius :
nếu tồn tại
nếu , hay với mọi
Có thể chứng minh được rằng với và tính được bằng cách sử dụng một thuật toán tương tự với Sàng nguyên tố:
mu[1] = 1;
for (int i = 1; i <= N; i++)
for (int j = 2*i; j <= N; j += i)
mu[j] -= mu[i];
Vỡi mỗi , ta gọi hàm tổng là tổng các với là ước của :
Phi hàm Euler (Euler totient function): số lượng các số tự nhiên nhỏ hơn hoặc bằng và nguyên tố cùng nhau với (hay số lượng các số ). Các bạn cũng có thể sử dụng sàng để tính :
for (int i = 1; i <= N; i++) phi[i] = i;
for (int i = 2; i <= N; i++)
if (phi[i] == i)
for (int j = i; j <= N; j += i)
phi[j] -= phi[j]/i;
Ta định nghĩa Dirichlet Convolution là một phép toán với 2 hàm và :
hay
Có thễ dễ dàng chứng minh phép toán này có tính giao hoán và kết hợp:
Ta có nhận xét rằng:
Từ đó suy ra:
hay
- đây gọi là Công thức nghịch đảo Mobius
Tính
.
Dễ thấy cách tiếp cận đơn giản nhất cho bài toán này là duyệt tất cả các cặp . Độ phức tạp của thuật toán này là , với là số phép toán tối đa khi tính . Chúng ta sẽ đi tìm một lời giải tối ưu hơn sử dụng những kiến thức ở trên.
Nhận xét rằng với mọi .
Như vậy, biểu thức trên có thể viết lại thành
.
Với là số lượng cặp thỏa mãn .
Công việc tính thật sự không hề đơn giản.
Ta để ý rằng .
Ta viết lại thành
với
Giờ chúng ta sẽ tìm cách phân tích thành hàm tổng của hàm nào đó, tức là:
.
Ứng dụng công thức nghịch đảo Mobius, bạn có thể tìm được:
Một kết quả rất đẹp trong bài toán này là . Tuy nhiên, nếu không biết tính chất này thì khi đã biết được và , ta có thể tính bằng sàng như sau:
for (int i = 1; i <= N; i++)
for (int j = i; j <= N; j += i)
f[j] += h[i] * mu[j/i];
Đoạn code trên chạy trong thời gian (tham khảo Độ phức tạp thời gian)
Viết lại một lần nữa ta được:
Đặt . Hàm này có ý nghĩa là số lượng cặp thỏa mãn là bội của . Đến đây mọi việc đã đơn giản hơn rất nhiều. Các bạn chỉ cần tìm số lượng cặp mà và đều là bội của . Từ đến có bội của , nên sẽ có cặp như vậy.
Vậy (4) trở thành .
Dễ dàng chứng minh là với chạy từ đến chỉ có giá trị nên ta có thể duyệt từng giá trị của và cộng vào kết quả.
Bằng tổng tiền tố các bạn có thể truy vấn được trong và trong :
for (int i = 1,j; i <= n; i = j + 1) {
j = n / (n/i); //vị trí j xa i nhất mà n/i=n/j
res += n/i*(n/i - 1)/2 * (Sf[j] - Sf[i-1]);//Sf[i]=f[1]+f[2]+f[3]+...+f[i]
}
Như vậy thuật toán trên có độ phức tạp với là số test.
Bài toán tổng quát hơn của bài toán trên là tính với (nên) là một hàm nhân tính. Ví dụ muốn tính thì .
Các bước tính toán gần như giống với bài toán trên.
Cho dãy số . Tìm số bộ ba () có . và
Ta đưa đề bài này về bài toán: tính
Viết lại biểu thức trên:
, ở đây là số lượng bộ ba có .
Tìm bằng công thức nghịch đảo Mobius.
Ở bài toán này chính bằng , việc chứng minh mình cũng xin nhường lại cho bạn đọc.
Lúc này .
.
Tính là số bộ ba có là bội của .
Duyệt lại và tính .
Nếu các bạn muốn tìm hiểu sâu và đầy đủ hơn về các bài toán liên quan thì có thể tham khảo http://mathcircle.berkeley.edu/original/Multiplicative.pdf