Xử Lý Đối Tượng Khó Nuốt Trong Lý Thuyết Số

Xử Lý Đối Tượng Khó Nuốt Trong Lý Thuyết Số

Chào mừng đến với bài thứ 3 trong series "Toán học" của mình!

Một số đối tượng trong toán học, như tổng các chữ số của một số hay số các ước của một số, rất hay được sử dụng trong các vấn đề lập trình, ngoài ra chúng đặc biệt hữu ích trong mật mã học (cryptography). Tất nhiên trong những đối tượng đó cũng có một vài cái "khó nuốt". Vì vậy, hôm nay chúng ta sẽ bàn về khía cạnh xử lí những đối tượng này hiệu quả nhất có thể!

Let's go!

1. Tổng các chữ số của một số

Thật ra mình không cần phải nói nhiều về món này, chỉ là nó khá đơn giản, nhưng lại được sử dụng vào rất nhiều thứ.

Tổng các chữ số của n thường được kí hiệu là S(n)

Sau đây là pseudocode (mã giả) minh họa cách tính S(n):

sum = 0
while (n > 0) {
    // cộng chữ số đứng cuối vào sum
    sum = sum + (n % 10)
    // bỏ chữ số cuối của n
    n = n / 10
}

ĐPT: O(log n)

Một vài ứng dụng của S(n):

  • Kiểm tra nhanh tính chia hết của n cho một vài số (ví dụ như 3, 9).
  • Làm nguyên liệu quan trọng trong các thuật toán sinh giá trị tổng kiểm cho các máy tính đời đầu.

2. Số các ước của một số

Đây là bài toán mà nhiều bạn có lẽ đã chạm trán khi mới bắt đầu đặt chân lên mảnh đất lập trình. Số các ước của số n thường được kí hiệu là σ0(n)

Sau đây mình xin giới thiệu vài cách tiếp cận vấn đề này, từ chậm nhất đến hiệu quả nhất. Mình đoán là ít nhiều các bạn cũng sẽ có chung ý tưởng với những cách tiếp cận sau đây

Naive Approach: Ta duyệt tất cả các số từ 1 đến n. Nếu n chia hết cho số đó tức là số đó là ước của n, ta tăng kết quả lên 1.

count = 0
divi = 1
while (divi <= n) {
    if (n % divi == 0) {
        // đã tìm thấy 1 ước, tăng count
        count = count + 1
    }
    // tăng divi
    divi = divi + 1
}

ĐPT: O(n), hiệu quả với n ≤ 106

Efficient Approach 1: Ta để ý rằng với số a là 1 ước của n, ta luôn có số b sao cho a x b = n.

Nếu a ≤ b thì a x a ≤ a x b = n, tức là a ≤ √n. Điều này có nghĩa là ta sẽ chỉ cần duyệt đến √n.

count = 0
divi = 1
while (divi <= sqrt(n)) {
    if (n % divi == 0) {
        if (divi != n / divi) {
            // đây là 2 ước khác nhau của n, nên chúng ta tăng count lên 2
            count = count + 2
        }
        else {// vì divi = n / divi nên chỉ tăng count lên 1
            cout = count + 1
        }    
    }
    divi = divi + 1
}

ĐPT: O(√n), hiệu quả với n ≤ 1012

Efficient Approach 2: Ta sẽ lợi dụng điều sau:

Số n có thể được phân tích thành các thừa số nguyên tố: n = p1e1p2e2...pkek. Khi đó ta nhận thấy rằng 1 ước của n sẽ có dạng: p1d1p2d2...pkdk (0 ≤ di ≤ ei)

Nếu các bạn còn nhớ quy tắc nhân (tại đây), các bạn sẽ tính được σ0(n) bằng cách "chọn" các hệ số d1, d2, ..., dk như sau:

  • Với hệ số d1, có e+ 1 cách chọn: Các số từ 0 đến e1
  • Với hệ số d2, có e+ 1 cách chọn: Các số từ 0 đến e2

...

Ta có thể chắc chắn rằng mỗi cách chọn như vậy sẽ cho ra một ước số phân biệt của n

Vậy σ0(n) = (e+ 1)(e+ 1)...(e+ 1)

Với công thức trên, ta có ý tưởng đếm như sau:

  • Duyệt tất cả các số nguyên tố đến √n. Nếu n chia hết cho số nguyên tố đó, phân tích xem trong n "chứa" được bao nhiêu số nguyên tố đó. Sau đó nhân vào kết quả (và nhớ cộng thêm 1!)
  • Kiểm tra xem đến cuối n có phải là 1 không. Nếu đúng thì trả kết quả, còn ngược lại, n lớn hơn 1 thì chắc chắn nó là một số nguyên tố lớn hơn √n mà ta đã bỏ sót trong bước trên. Đến đây thì nhân 2 vào kết quả là xong.

ĐPT: O(√n), hiệu quả với n ≤ 1012 (có thể tối ưu hóa đến O(√n / 6))

Efficient Approach 3: Bây giờ thì các bạn muốn "nâng độ khó cho game", đếm số ước của n với n ≤ 1018. Điều này là hoàn toàn khả thi, nó chỉ vận dụng ý tưởng của cách tiếp cận trên:

  • Thay vì duyệt các số nguyên tố đến √n, ta chỉ cần duyệt đến n1/3 (căn bậc 3 của n) để tính được với n lớn.
  • Đến đây, sau khi phân tích hết các ước nguyên tố không lớn hơn n1/3 của n, nếu n lớn hơn 1, ta có 3 khả năng sau:
    • n là số nguyên tố: Nhân 2 vào kết quả
    • n là bình phương của 1 số nguyên tố: Nhân 3 vào kết quả
    • n là tích của hai số nguyên tố: Nhân 4 vào kết quả

Tuy nhiên, trong một số trường hợp, khi ta hoàn thành bước đầu, n vẫn sẽ rất lớn, vì thế nên ta không thể áp dụng những thuật toán kiểm tra nguyên tố bình thường được. Đến đây thì tốt hơn hết là ta nên dùng những thuật toán kiểm tra nguyên tố nhanh, như kiểm tra nguyên tố Miller-Rabin.

ĐPT: O(n1/3), hiệu quả với n ≤ 1018

Các bạn cũng có thể xem thêm về cách tiếp cận này ở đây (Codeforces) hoặc đây (GeeksforGeeks)

Mở rộng: Chúng ta cũng có thể tối ưu hóa thuật toán trên đến O(n1/4), O(n1/5), ..., nhưng đến bước cuối thì sẽ có nhiều trường hợp phải xét hơn. Ngoài ra thì những ngôn ngữ như C++ chỉ có giới hạn long đến 263 - 1 (= 9 x 1018) nên theo mình, O(n1/3) đã là quá đủ rồi.

3. Tổng các ước của một số

Lại thêm một bài toán kinh điển. Tổng các ước của số n thì thường được kí hiệu là σ1(n)

Ứng với mỗi cách tiếp cận cho vấn đề tính số các ước ở trên, mình sẽ giới thiệu cách tương ứng đối với vấn đề này, vì thực ra chúng cũng từa tựa như nhau!

Naive Approach: Ta duyệt tất cả các số từ 1 đến n. Nếu n chia hết cho số đó tức là số đó là ước của n, ta cộng số đó vào tổng.

ĐPT: O(n), hiệu quả với n ≤ 106

Efficient Approach 1: Ta chỉ cần duyệt đến √n

sum = 0
divi = 1
while (divi <= sqrt(n)) {
    if (n % divi == 0) {
        if (divi != n / divi) {
            // đây là 2 ước khác nhau của n, nên chúng ta cộng cả 2 ước vào sum
            sum = sum + divi + n / divi
        }
        else {// vì divi = n / divi nên chỉ cộng 1 số
            sum = sum + divi
        }    
    }
    divi = divi + 1
}

ĐPT: O(√n), hiệu quả với n ≤ 1012

Efficient Approach 2: Với n = p1e1p2e2...pkek, ta sẽ tìm ra được công thức sau: 

σ1(n) = (1 + p1 + p12 + ... + p1e1) x (1 + p2 + p22 + ... + p2e2) x ... x (1 + pk + pk2 + ... + pkek)

hay σ1(n) = ((p1e1+1 - 1) / (p1 - 1)) x ((p2e2+1 - 1) / (p2 - 1)) x ... x ((pkek+1 - 1) / (pk - 1))

Mỗi thừa số trong công thức trên đều có thể được tính trong log ei, nên sẽ không ảnh hưởng đến ĐPT toàn cục.

ĐPT: O(√n), hiệu quả với n ≤ 1012 (có thể tối ưu hóa đến O(√n / 6))

Efficient Approach 3: Lại sử dụng công thức trên, nhưng chỉ duyệt đến n1/3. Mình sẽ để phần còn lại cho các bạn động não nhé!

ĐPT: O(n1/3), hiệu quả với n ≤ 1018

4. Hàm phi Euler

Đây là một trong những đối tượng lạ hơn, nhưng cũng phần nào đáng chú ý hơn những đối tượng trên, vì nó có một tính chất "hiếm" mà ít đối tượng nào khác sở hữu.

Hàm phi Euler của n được định nghĩa là số các số không lớn hơn n và nguyên tố cùng nhau với n (2 số a, b được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1), thường được kí hiệu là φ(n).

Với định nghĩa rõ ràng như trên, có thể các bạn đã nghĩ đến hướng làm "trâu" như sau:

Naive Approach: Ta duyệt tất cả các số từ 1 đến n. Nếu số đó nguyên tố cùng nhau với n, ta tăng kết quả thêm 1.

ĐPT: O(n log n), hiệu quả với n ≤ 105

Tuy nhiên, nếu chịu khó phân tích một chút (hoặc tra Google :) ), các bạn sẽ tìm được 2 công thức thú vị sau đây. Trong những bài viết tiếp theo mình sẽ chứng minh chúng, tạm thời thì cứ thừa nhận những kết quả này đã nha! ;)

  • φ(pk) = pk - pk - 1, với p là một số nguyên tố.
  • φ(mn) = φ(m) x φ(n), với m, n là cặp số nguyên tố cùng nhau. Tính chất này là tính "hiếm" mình đã nhắc tới, và nó được gọi là "nhân tính".

Như vậy, với n = p1e1p2e2...pkek, chúng ta sẽ có:

φ(n) = φ(p1e1p2e2...pkek) = φ(p1e1) x φ(p2e2) x ... x φ(p2e2)

= (p1e1 - p1e1 - 1) x (p2e2 - p2e2 - 1) x ... x (pkek - pkek - 1)

= n x (1 - 1 / p1) x (1 - 1 / p2) x ... x (1 - 1 / pk)

Từ đây chúng ta sẽ có những hướng tiếp cận hiệu quả sau:

Efficient Approach 1:

// pseudocode để tính hàm phi Euler
phi = n
prime = 2
while (prime <= sqrt(n)) { // duyệt các số nguyên tố đến căn n
    if (n % prime == 0) {
        while (n % prime == 0) n = n / prime // phân tích cho đến khi prime không có trong n nữa
        phi = phi - phi / prime // = phi * (1 - 1 / prime)
    }
    if (n > 1) { // n đang là số nguyên tố
        phi = phi - phi / n
    }
}

ĐPT: O(√n), hiệu quả với n ≤ 1012

Efficient Approach 2 and 3: Ta cũng sẽ đi theo hướng phân tích thừa số nguyên tố giống như khi tính số các ước và tổng các ước. Công thức thì đã có sẵn rồi!

ĐPT: O(√n) hoặc O(n1/3)

Tạm kết

Trên đây là một vài đối tượng khó nhằn trong toán học cũng hay xuất hiện trong lập trình, và những cách khác nhau để trị chúng.

Hy vọng bài viết này giúp ích các bạn trong việc xử lí những vấn đề được đề cập đến trong này!