Khóa học CTDL và GT

Bài 2.4: Phương pháp bình phương nhân và luỹ thừa nhanh

Chào mừng các bạn quay trở lại với series blog về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ khám phá một kỹ thuật tính toán cực kỳ hữu ích và hiệu quả trong lập trình, đặc biệt là trong lập trình thi đấu: Phương pháp bình phương nhân hay còn gọi là Luỹ thừa nhanh (Binary Exponentiation / Exponentiation by Squaring).

Vấn đề: Tính a mũ b một cách hiệu quả

Bạn được yêu cầu tính giá trị của $a^b$, trong đó $a$ và $b$ có thể là những số rất lớn.

Cách làm ngây thơ và trực quan nhất là gì? Đơn giản là nhân $a$ với chính nó $b$ lần:

long long naive_power(long long base, long long exp) {
    long long res = 1;
    for (int i = 0; i < exp; ++i) {
        res *= base; // Nhân base exp lần
    }
    return res;
}

Cách này có vẻ đúng, nhưng hãy nghĩ về độ phức tạp của nó. Nếu $b$ là một số rất lớn (ví dụ $10^9$), chúng ta sẽ thực hiện $10^9$ phép nhân. Điều này cực kỳ chậm! Hơn nữa, giá trị của $a^b$ có thể tăng lên rất nhanh và vượt quá giới hạn lưu trữ của các kiểu dữ liệu thông thường như long long, dẫn đến tình trạng tràn số (overflow).

Làm thế nào để giải quyết vấn đề này? Chúng ta cần một phương pháp nhanh hơn, và đó chính là lúc Bình phương nhân toả sáng!

Ý tưởng cốt lõi: Khai thác tính chất của số mũ

Phương pháp bình phương nhân dựa vào các tính chất đơn giản của số mũ:

1. $a^{2k} = (a^k)^2$
2. $a^{2k+1} = a \cdot a^{2k} = a \cdot (a^k)^2$
3. $a^0 = 1$

Những tính chất này cho thấy rằng chúng ta có thể tính $a^b$ bằng cách liên tục bình phương kết quả trung gian và nhân thêm $a$ nếu số mũ là lẻ. Điều này gợi ý một cách tiếp cận dựa trên biểu diễn nhị phân của số mũ $b$.

Hãy xem xét số mũ $b$ ở dạng nhị phân. Ví dụ, $b = 13$. Dạng nhị phân của 13 là $1101_2$. $13 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 8 + 4 + 0 + 1$. Vậy, $a^{13} = a^{8+4+1} = a^8 \cdot a^4 \cdot a^1$.

Nhận thấy rằng $a^8 = (a^4)^2 = ((a^2)^2)^2$ và $a^4 = (a^2)^2$. Điều này cho phép chúng ta tính các luỹ thừa của $a$ với số mũ là luỹ thừa của 2 ($a^1, a^2, a^4, a^8, \dots$) bằng cách lặp đi lặp lại thao tác bình phương.

Cụ thể, để tính $a^b$, chúng ta có thể duyệt qua các bit trong biểu diễn nhị phân của $b$ từ phải sang trái (từ bit 0 đến bit cao nhất).

• Chúng ta duy trì một biến current_power ban đầu bằng $a$. Ở mỗi bước, chúng ta bình phương current_power. Biến này sẽ lần lượt nhận giá trị $a^1, a^2, a^4, a^8, \dots$.
• Chúng ta duy trì một biến result ban đầu bằng 1.
• Khi xét bit thứ $i$ của $b$ (tương ứng với $2^i$):
  • Nếu bit thứ $i$ là 1, điều đó có nghĩa là $a^{2^i}$ cần được đóng góp vào kết quả cuối cùng (vì $b$ có chứa $2^i$ trong tổng nhị phân của nó). Chúng ta nhân result với giá trị hiện tại của current_power (là $a^{2^i}$).
  • Sau khi xử lý bit thứ $i$ (duyệt $b$ từ phải sang trái), chúng ta chuyển sang xét bit thứ $i+1$. Để chuẩn bị cho bước này, chúng ta bình phương current_power (từ $a^{2^i}$ thành $a^{2^{i+1}}$) và dịch phải $b$ đi 1 bit (loại bỏ bit đã xét).

Quá trình này dừng lại khi $b$ trở thành 0.

Ví dụ minh hoạ: Tính $3^{13}$

$b = 13$. Dạng nhị phân của 13 là $1101_2$.

$b$ đã bằng 0. Dừng lại. Kết quả cuối cùng là result = 1594323. Kiểm tra lại: $3^{13} = 1594323$. Chính xác!

Cách tiếp cận này cho thấy chúng ta chỉ cần thực hiện số phép nhân tỷ lệ với số bit của $b$, tức là $\log_2 b$ phép bình phương và tối đa $\log_2 b$ phép nhân với kết quả.

Cài đặt: Phương pháp Bình phương nhân (Iterative)

Đây là cách cài đặt phổ biến và hiệu quả nhất của phương pháp bình phương nhân sử dụng vòng lặp:

#include <iostream>

long long power(long long base, long long exp) {
    long long res = 1; // Kết quả ban đầu là a^0 = 1

    // Lặp cho đến khi số mũ (exp) về 0
    while (exp > 0) {
        // Kiểm tra bit cuối cùng của exp.
        // Nếu bit cuối là 1 (exp là số lẻ), nghĩa là lũy thừa base^(2^i)
        // tương ứng với bit này cần được nhân vào kết quả.
        if (exp % 2 == 1) {
            res *= base;
        }

        // Bình phương base để chuẩn bị cho bit tiếp theo (lũy thừa của 2 tăng lên)
        base *= base;

        // Dịch phải exp 1 bit (tương đương exp /= 2)
        // để chuyển sang xét bit tiếp theo.
        exp /= 2;
    }

    return res;
}

int main() {
    long long base = 3;
    long long exp = 13;
    long long result = power(base, exp);
    std::cout << base << "^" << exp << " = " << result << std::endl; // Output: 3^13 = 1594323

    base = 2;
    exp = 10;
    result = power(base, exp);
    std::cout << base << "^" << exp << " = " << result << std::endl; // Output: 2^10 = 1024

    return 0;
}

Giải thích code:

• res: Biến lưu trữ kết quả cuối cùng. Khởi tạo bằng 1 ($a^0$).
• base: Biến lưu trữ giá trị cơ sở, ban đầu là $a$. Trong vòng lặp, nó sẽ lần lượt giữ các giá trị $a^1, a^2, a^4, a^8, \dots$.
• Vòng while (exp > 0): Lặp cho đến khi toàn bộ các bit của exp được xử lý.
• if (exp % 2 == 1): Kiểm tra bit cuối cùng của exp. exp % 2 == 1 tương đương với việc bit 0 của exp là 1. Nếu đúng, nhân res với base. Tại sao? Bởi vì khi exp có bit cuối cùng là 1, nó đại diện cho một lũy thừa của $a$ mà chúng ta cần nhân vào kết quả (ví dụ $a^1, a^3=a^{2+1}, a^5=a^{4+1}, \dots$). Khi chúng ta ở bit thứ $i$ (tương ứng $2^i$), base đang giữ giá trị $a^{2^i}$. Nếu bit thứ $i$ của số mũ gốc là 1, ta nhân $a^{2^i}$ vào kết quả.
• base *= base;: Bình phương base. Nếu trước đó base là $a^{2^i}$, sau phép này nó sẽ là $(a^{2^i})^2 = a^{2^{i+1}}$. Điều này chuẩn bị giá trị base cho việc xử lý bit tiếp theo của exp.
• exp /= 2;: Dịch phải exp đi 1 bit. Điều này loại bỏ bit cuối cùng đã xét và chuyển sang xét bit tiếp theo (bit 1, rồi bit 2, ...).

Cài đặt: Phương pháp Bình phương nhân (Recursive)

Phương pháp này cũng có thể được cài đặt một cách đệ quy dựa trên tính chất $a^{2k} = (a^k)^2$ và $a^{2k+1} = a \cdot (a^k)^2$.

#include <iostream>

long long power_recursive(long long base, long long exp) {
    // Trường hợp cơ sở: a^0 = 1
    if (exp == 0) {
        return 1;
    }

    // Nếu số mũ là chẵn
    if (exp % 2 == 0) {
        // Tính a^(exp/2) trước
        long long half_power = power_recursive(base, exp / 2);
        // Kết quả là (a^(exp/2))^2
        return half_power * half_power;
    } else { // Nếu số mũ là lẻ
        // Tính a^((exp-1)/2)
        long long half_power = power_recursive(base, (exp - 1) / 2);
        // Kết quả là a * (a^((exp-1)/2))^2
        return base * half_power * half_power;
    }
}

int main() {
    long long base = 3;
    long long exp = 13;
    long long result = power_recursive(base, exp);
    std::cout << base << "^" << exp << " = " << result << std::endl; // Output: 3^13 = 1594323

    base = 2;
    exp = 10;
    result = power_recursive(base, exp);
    std::cout << base << "^" << exp << " = " << result << std::endl; // Output: 2^10 = 1024

    return 0;
}

Giải thích code:

• if (exp == 0): Trường hợp cơ sở của đệ quy. Khi số mũ bằng 0, kết quả là 1.
• if (exp % 2 == 0): Nếu số mũ chẵn, ta tính half_power = base^(exp/2) bằng cách gọi đệ quy. Sau đó, kết quả là half_power * half_power.
• else: Nếu số mũ lẻ, ta tính half_power = base^((exp-1)/2) bằng cách gọi đệ quy. Số mũ (exp-1)/2 là phần nguyên của exp/2, loại bỏ đi 1 ở số mũ lẻ. Sau đó, kết quả là base * half_power * half_power. Ví dụ, $a^5 = a \cdot a^4 = a \cdot (a^2)^2$. Ở đây, base là $a$, half_power là $a^2$.

Cả hai cách cài đặt iterative và recursive đều có độ phức tạp thời gian là $O(\log b)$, vì ở mỗi bước hoặc mỗi lần gọi đệ quy, số mũ $b$ được giảm đi khoảng một nửa. Điều này là cực kỳ nhanh so với độ phức tạp $O(b)$ của cách làm ngây thơ.

Độ phức tạp không gian: Cách iterative có độ phức tạp không gian $O(1)$ (chỉ dùng vài biến). Cách recursive có độ phức tạp không gian $O(\log b)$ do cần stack cho các lời gọi đệ quy. Do đó, cách iterative thường được ưa chuộng hơn trong thực tế, đặc biệt với các số mũ rất lớn.

Ứng dụng quan trọng: Luỹ thừa nhanh với Modulo

Như đã đề cập, $a^b$ có thể trở thành một số khổng lồ rất nhanh, vượt quá khả năng lưu trữ. Tuy nhiên, trong rất nhiều bài toán (ví dụ: cryptography, number theory, lập trình thi đấu), chúng ta chỉ cần tìm kết quả của $a^b \pmod m$, tức là số dư khi $a^b$ chia cho một số nguyên $m$.

May mắn thay, chúng ta có thể áp dụng phương pháp bình phương nhân kết hợp với tính chất của phép modulo: $(x \cdot y) \pmod m = ((x \pmod m) \cdot (y \pmod m)) \pmod m$

Điều này có nghĩa là chúng ta có thể áp dụng phép modulo tại mỗi bước nhân trong thuật toán bình phương nhân để giữ cho các giá trị trung gian luôn nằm trong phạm vi $[0, m-1]$, tránh tràn số.

Cài đặt Luỹ thừa nhanh với Modulo (Iterative)

#include <iostream>

// Hàm tính (base ^ exp) % modulus
long long power_mod(long long base, long long exp, long long modulus) {
    long long res = 1; // Kết quả ban đầu là a^0 = 1

    // Đảm bảo base nằm trong phạm vi [0, modulus-1]
    // Rất quan trọng nếu base ban đầu là số âm hoặc rất lớn
    base %= modulus;
    if (base < 0) base += modulus; // Xử lý trường hợp base âm

    // Lặp cho đến khi số mũ (exp) về 0
    while (exp > 0) {
        // Nếu bit cuối cùng của exp là 1 (exp là số lẻ)
        // Nhân kết quả hiện tại với base^(lũy thừa của 2 tương ứng) và lấy modulo
        if (exp % 2 == 1) {
            res = (res * base) % modulus;
        }

        // Bình phương base và lấy modulo
        // base sẽ lần lượt là (a^1)%m, (a^2)%m, (a^4)%m, ...
        base = (base * base) % modulus;

        // Dịch phải exp 1 bit (tương đương exp /= 2)
        exp /= 2;
    }

    return res;
}

int main() {
    long long base = 3;
    long long exp = 100;
    long long modulus = 1000000007; // Một số nguyên tố lớn thường dùng

    long long result = power_mod(base, exp, modulus);
    // 3^100 mod 1000000007
    // Kết quả cần tính sẽ không bị tràn số

    std::cout << base << "^" << exp << " % " << modulus << " = " << result << std::endl; // Output: 3^100 % 1000000007 = 519432012

    base = 2;
    exp = 60;
    modulus = 1000;
    result = power_mod(base, exp, modulus);
    // 2^60 mod 1000
    std::cout << base << "^" << exp << " % " << modulus << " = " << result << std::endl; // Output: 2^60 % 1000 = 0 (vì 2^10 chia hết cho 1000)

    return 0;
}

Giải thích code (Modular Iterative): Thuật toán hoàn toàn tương tự như bản iterative không có modulo, chỉ thêm phép % modulus sau mỗi phép nhân (res * base và base * base). Điều này đảm bảo các giá trị res và base luôn được giữ trong phạm vi hợp lý, tránh tràn số ngay cả khi a và b rất lớn.

Lưu ý thêm dòng base %= modulus; if (base < 0) base += modulus;. Dòng này rất quan trọng để đảm bảo base ban đầu nằm trong phạm vi hợp lệ cho phép modulo, đặc biệt nếu base có thể là số âm (trong C++, phép % với số âm có thể cho kết quả âm).

Cài đặt Luỹ thừa nhanh với Modulo (Recursive)

Tương tự, bản đệ quy cũng chỉ cần thêm phép modulo.

#include <iostream>

// Hàm tính (base ^ exp) % modulus
long long power_mod_recursive(long long base, long long exp, long long modulus) {
    // Đảm bảo base nằm trong phạm vi [0, modulus-1]
    base %= modulus;
     if (base < 0) base += modulus;

    // Trường hợp cơ sở: a^0 = 1
    if (exp == 0) {
        return 1;
    }

    // Nếu số mũ là chẵn
    if (exp % 2 == 0) {
        // Tính (base^(exp/2)) % modulus
        long long half_power = power_mod_recursive(base, exp / 2, modulus);
        // Kết quả là ((base^(exp/2)) % modulus * (base^(exp/2)) % modulus) % modulus
        return (half_power * half_power) % modulus;
    } else { // Nếu số mũ là lẻ
        // Tính (base^((exp-1)/2)) % modulus
        long long half_power = power_mod_recursive(base, (exp - 1) / 2, modulus);
        // Kết quả là (base % modulus * (base^((exp-1)/2)) % modulus * (base^((exp-1)/2)) % modulus) % modulus
        return (((base * half_power) % modulus) * half_power) % modulus;
        // Hoặc gọn hơn: return (base * ((half_power * half_power) % modulus)) % modulus;
    }
}

int main() {
    long long base = 3;
    long long exp = 100;
    long long modulus = 1000000007;

    long long result = power_mod_recursive(base, exp, modulus);
    std::cout << base << "^" << exp << " % " << modulus << " = " << result << std::endl; // Output: 3^100 % 1000000007 = 519432012

    base = 2;
    exp = 60;
    modulus = 1000;
    result = power_mod_recursive(base, exp, modulus);
    std::cout << base << "^" << exp << " % " << modulus << " = " << result << std::endl; // Output: 2^60 % 1000 = 0

    return 0;
}

Giải thích code (Modular Recursive): Tương tự bản recursive không có modulo, chỉ thêm phép % modulus sau mỗi phép nhân.

Phương pháp luỹ thừa nhanh với modulo là một công cụ cực kỳ mạnh mẽ và được sử dụng rộng rãi trong các bài toán cần tính toán luỹ thừa với số mũ lớn trên trường số nguyên modulo $m$.

Bài tập ví dụ:

Phân tích thừa số nguyên tố

Hãy phân tích một số nguyên dương N thành thừa số nguyên tố.

Input Format

Số nguyên dương N (2 ≤ N ≤ 10^16).

Constraints

Không có ràng buộc thêm.

Output Format

Phân tích thừa số nguyên tố của N, xem ví dụ để hiểu rõ hơn về format.

Sample Input 0

30

Sample Output 0

2^1 * 3^1 * 5^1

Chào bạn, đây là hướng dẫn giải bài Phân tích thừa số nguyên tố bằng C++ một cách ngắn gọn:

1. Kiểu dữ liệu: Vì N có thể lên tới 10^16, bạn cần sử dụng kiểu dữ liệu long long để lưu trữ N và các thừa số nguyên tố có thể tìm được.

2. Thuật toán chính (Phân tích thử): Thuật toán phổ biến và hiệu quả cho giới hạn N này là phân tích thử (trial division).

   • Duyệt qua các số nguyên i từ nhỏ nhất đến lớn.
   • Đối với mỗi i, kiểm tra xem N có chia hết cho i không.
   • Nếu N chia hết cho i, đếm số lần chia hết (count), đồng thời chia N cho i cho đến khi N không còn chia hết cho i nữa. Lưu lại thừa số i với số mũ count.
   • Tiếp tục quá trình với giá trị N đã được cập nhật.

3. Tối ưu hóa thuật toán:

   • Xử lý thừa số 2 riêng: Bắt đầu bằng việc kiểm tra và loại bỏ hết các thừa số 2 khỏi N. Điều này giúp ta chỉ cần xét các thừa số lẻ từ 3 trở đi.
   • Kiểm tra các thừa số lẻ: Duyệt các số i bắt đầu từ 3, tăng dần 2 đơn vị (3, 5, 7, 9... nhưng số 9 sẽ không chia hết nếu 3 đã bị loại bỏ, nên ta chỉ cần kiểm tra các số lẻ).
   • Giới hạn vòng lặp: Bạn chỉ cần kiểm tra các thừa số i lên đến căn bậc hai của N (sau khi N đã được loại bỏ các thừa số nhỏ hơn). Lý do là nếu N còn một thừa số nguyên tố p lớn hơn sqrt(N), thì N phải bằng p * q, và q phải nhỏ hơn sqrt(N), và q đã bị loại bỏ trong quá trình kiểm tra các thừa số nhỏ hơn hoặc bằng sqrt(N). Lưu ý: để tránh dùng số thực và sai số, điều kiện vòng lặp thường là i * i <= N.

4. Xử lý thừa số cuối cùng: Sau khi vòng lặp kiểm tra đến sqrt(N) kết thúc, nếu N vẫn còn lớn hơn 1, thì giá trị N hiện tại chính là một thừa số nguyên tố (lớn hơn sqrt(N) ban đầu) và số mũ của nó là 1.

5. Định dạng đầu ra:

   • Lưu trữ các cặp (thừa số, số mũ) tìm được (ví dụ: dùng std::vector<std::pair<long long, int>>).
   • In các cặp này theo định dạng thừa_số^số_mũ.
   • In ký tự * giữa các thừa số, trừ thừa số cuối cùng.

Làm thêm nhiều bài tập miễn phí tại đây