Lũy thừa nhị phân

đã đăng vào 23, Tháng 12, 2025, 10:08

Lũy thừa nhị phân (Binary Exponentiation)

1) Bài toán

Tính lũy thừa ~a^n~ với ~n \ge 0~.

Cách ngây thơ cần ~n-1~ phép nhân ~\Rightarrow O(n)~.
Lũy thừa nhị phân giảm xuống còn ~O(\log n)~ phép nhân nhờ: $$ a^{b+c}=a^b\cdot a^c,\qquad a^{2b}=(a^b)^2 $$

2) Ý tưởng cốt lõi

Viết ~n~ ở hệ nhị phân: $$ n=\sum_{i=0}^{k} \texttt{bit}_i\cdot 2^i,\quad \texttt{bit}_i\in\{0,1\} $$ Khi đó: $$ a^n=\prod_{\texttt{bit}_i=1} a^{2^i} $$

Ta tạo dãy ~a, a^2, a^4, a^8, \dots~ bằng bình phương liên tiếp, và chỉ nhân vào kết quả khi bit tương ứng của ~n~ bằng ~1~.

Độ phức tạp:

Thời gian: ~O(\log n)~
Bộ nhớ: ~O(1)~ (bản lặp)

3) Công thức đệ quy (Exponentiation by Squaring)

$$ a^n= \begin{cases} 1 & (n=0)\\ \left(a^{\lfloor n/2\rfloor}\right)^2 & (n>0,\ n\ \text{chẵn})\\ \left(a^{\lfloor (n-1)/2\rfloor}\right)^2\cdot a & (n>0,\ n\ \text{lẻ}) \end{cases} $$

4) Ví dụ minh họa

Ví dụ: ~3^{13}~

Vì ~13=1101_2=8+4+1~, nên: $$ 3^{13}=3^8\cdot 3^4\cdot 3^1 $$

Tính lần lượt: $$ 3^1=3,\quad 3^2=9,\quad 3^4=81,\quad 3^8=6561 $$ Suy ra: $$ 3^{13}=6561\cdot 81\cdot 3 = 1594323 $$

5) Pseudocode

5.1) Bản lặp

$$ \begin{aligned} \texttt{binpow}(a,b):\quad &\\ \texttt{res} &\gets 1\\ \textbf{while } \texttt{b} > 0:\quad &\\ \quad \textbf{if } (\texttt{b}\ \&\ 1)=1:\quad & \texttt{res} \gets \texttt{res}\cdot \texttt{a}\\ \quad \texttt{a} &\gets \texttt{a}\cdot \texttt{a}\\ \quad \texttt{b} &\gets \texttt{b} \gg 1\\ \textbf{return } &\texttt{res} \end{aligned} $$

Ở đây ~\texttt{b} \& 1~ kiểm tra bit cuối của ~\texttt{b}~, và ~\texttt{b} \gg 1~ là dịch phải ~1~ bit (tức chia ~2~ lấy phần nguyên).

6) Code mẫu (C++17 / Python 3)

6.1) Không modulo

C++17 (bản lặp)

#include <bits/stdc++.h>
using namespace std;

// Tính a^b với b >= 0.
// Lưu ý: có thể overflow nếu kết quả vượt giới hạn của long long.
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1LL) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

Python 3 (bản lặp)

def binpow(a: int, b: int) -> int:
    # Tính a^b với b >= 0 (Python int không lo overflow).
    res = 1
    while b > 0:
        if b & 1:
            res *= a
        a *= a
        b >>= 1
    return res

6.2) Có modulo ~m~

Ta dùng tính chất: $$ (x\cdot y)\bmod m = \big((x\bmod m)\cdot (y\bmod m)\big)\bmod m $$

C++17

#include <bits/stdc++.h>
using namespace std;

long long binpow_mod(long long a, long long b, long long m) {
    a %= m;
    long long res = 1 % m;
    while (b > 0) {
        if (b & 1LL) res = (res * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}

Python 3

def binpow_mod(a: int, b: int, m: int) -> int:
    a %= m
    res = 1 % m
    while b > 0:
        if b & 1:
            res = (res * a) % m
        a = (a * a) % m
        b >>= 1
    return res

7) Tràn số khi nhân modulo (biến thể “nhân nhị phân”)

Nếu cần tính ~(a\cdot b)\bmod m~ mà ~a\cdot b~ có thể vượt ~64~-bit, ta thay phép nhân bằng cộng dồn theo bit:

$$ \begin{aligned} \texttt{mul_mod}(a,b,m):\quad &\\ \texttt{res} &\gets 0\\ \textbf{while } \texttt{b} > 0:\quad &\\ \quad \textbf{if } (\texttt{b}\ \&\ 1)=1:\quad & \texttt{res} \gets (\texttt{res}+\texttt{a})\bmod m\\ \quad \texttt{a} &\gets (\texttt{a}+\texttt{a})\bmod m\\ \quad \texttt{b} &\gets \texttt{b} \gg 1\\ \textbf{return } &\texttt{res} \end{aligned} $$

C++17:

#include <bits/stdc++.h>
using namespace std;

// (a*b)%m an toàn hơn khi a*b có thể tràn long long.
long long mul_mod(long long a, long long b, long long m) {
    a %= m;
    long long res = 0;
    while (b > 0) {
        if (b & 1LL) res = (res + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return res;
}

8) Sai lầm thường gặp

Quên lấy modulo sau mỗi phép nhân trong ~\texttt{binpow_mod}~ ~\Rightarrow~ tràn số/ra sai.
Dùng ~\texttt{int}~ thay vì ~\texttt{long long}~ khi ~\texttt{a}~, ~\texttt{b}~, ~\texttt{m}~ lớn.
Không chuẩn hóa ~\texttt{a} \gets \texttt{a}\bmod m~ ngay từ đầu.
Nhầm dịch bit: ~\texttt{b} \gg 1~ tương đương ~\left\lfloor \dfrac{\texttt{b}}{2}\right\rfloor~.
Với bài cần an toàn tuyệt đối khi nhân, hãy dùng ~\texttt{__int128}~ (C++) hoặc ~\texttt{mul_mod}~ ở trên.

9) Bài tập vận dụng

Viết hàm ~\texttt{binpow_mod}(a,b,m)~ với ~b~ đến ~10^{18}~.
Tính ~3^{10^{18}} \bmod (10^9+7)~.
Cho ~a,b,m\le 10^{18}~. Tính ~(a\cdot b)\bmod m~ không tràn bằng ~\texttt{mul_mod}~.
(Nâng cao) Tính Fibonacci ~F_n \bmod (10^9+7)~ bằng lũy thừa ma trận trong ~O(\log n)~.