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 f(n):N→C đượ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 n,m∈N ta có f(mn)=f(m)f(n)
Một số n phân tích ra thừa số nguyên tố sẽ có dạng n=p1a1p2a2p3a3…prar, với pi là ước nguyên tố của n.
Ký hiệu a∣b có nghĩa là a là ước của b, hay b chia hết cho a
Hàm định danh Dirichlete(n) (Dirichlet identity function):
e(n)=1 với n=1
e(n)=0 với n>1
I(n)=1 với mọi n∈N
id(n)=n với mọi n∈N
Hàm Mobiusμ(n):
μ(1)=1
μ(n)=0 nếu tồn tại ai>1
μ(n)=(−1)r nếu n=p1p2p3...pr, hay ai=1 với mọi i
Có thể chứng minh được rằng μ(n)=d∣n,d<n∑μ(d) với n>1 và tính được μ(n) 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 f(n), ta gọi hàm tổng Sf(n) là tổng các f(d) với d là ước của n: Sf(n)=d∣n∑f(d)
Phi hàm Eulerϕ(n) (Euler totient function): số lượng các số tự nhiên nhỏ hơn hoặc bằng n và nguyên tố cùng nhau với n (hay số lượng các số d:1≤d≤n,gcd(d,n)=1). Các bạn cũng có thể sử dụng sàng để tính phi(n):
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;
¶ Công thức nghịch đảo Mobius (Möbius inversion formula)
Ta định nghĩa Dirichlet Convolution là một phép toán với 2 hàm f(n) và g(n):
f∗g(n)=d1×d2=n∑f(d1)g(d2)
hay
f∗g(n)=d∣n∑f(d)g(n/d)
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:
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 (i,j). Độ phức tạp của thuật toán này là O(k∗n2), với k là số phép toán tối đa khi tính gcd. 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 1≤gcd(i,j)≤n với mọi 1≤i<j≤n.
Như vậy, biểu thức trên có thể viết lại thành
G=g=1∑n(g×cnt[g])(2).
Với cnt[g] là số lượng cặp (i,j) thỏa mãn gcd(i,j)=g.
Công việc tính cnt[g] thật sự không hề đơn giản.
Ta để ý rằng gcd(i,j)=g⇔gcd(gi,gj)=1.
Ta viết lại (2) thành
G=g=1∑n(h(g)×cnt[g]) với h(g)=g
Giờ chúng ta sẽ tìm cách phân tích h(n) thành hàm tổng S của hàm f(n) nào đó, tức là:
h(n)=Sf(n)=d∣n∑f(d).
Ứng dụng công thức nghịch đảo Mobius, bạn có thể tìm được:
f(n)=h(d)∗μ(n)
Một kết quả rất đẹp trong bài toán này là f(n)=φ(n). Tuy nhiên, nếu không biết tính chất này thì khi đã biết được h(n) và μ(n), ta có thể tính f(n) 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];
Đặt cnt2[d]=g⋮d∑cnt[g]. Hàm này có ý nghĩa là số lượng cặp (i,j) thỏa mãn gcd(i,j) là bội của d. Đế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 (i,j) mà i và j đều là bội của d. Từ 1 đến n có ⌊dn⌋ bội của d, nên sẽ có 2⌊dn⌋(⌊dn⌋−1) cặp (i,j) như vậy.
Vậy (4) trở thành G=d=1∑n2⌊dn⌋(⌊dn⌋−1)f(d).
Dễ dàng chứng minh là với d chạy từ 1 đến n chỉ có n giá trị ⌊dn⌋ nên ta có thể duyệt từng giá trị của ⌊dn⌋ và cộng 2⌊dn⌋(⌊dn⌋−1)k:⌊kn⌋=⌊dn⌋∑f(k) vào kết quả.
Bằng tổng tiền tố các bạn có thể truy vấn được k:⌊kn⌋=⌊dn⌋∑f(k) trong O(1) và G trong O(n):
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 O(NlogN+N∗T) với T là số test.
Bài toán tổng quát hơn của bài toán trên là tính G=i=1∑nj=i+1∑nh(gcd(i,j)) với h (nên) là một hàm nhân tính. Ví dụ muốn tính G=i=1∑nj=i+1∑ngcd3(i,j) thì h(n)=n3.
Các bước tính toán gần như giống với bài toán trên.