Elearning CodePath – CTP Online Judge

Tính Lũy Thừa

SPOW

🟢 Hard #General #Math #Number Theory

✅ Đã AC: 8 / 21 submissions

📘 Lời giải

## 💡 Tính Lũy Thừa

Bài toán yêu cầu tính $a^b \pmod{c}$, với $c = 10^9 + 7$. Đây là một bài toán kinh điển trong lập trình thi đấu, đòi hỏi phải sử dụng kỹ thuật **Lũy thừa nhị phân (Binary Exponentiation)** để xử lý số mũ $b$ rất lớn.

-----

### Subtask 1: $a \le 10^3$; $b \le 10^3$

Ý tưởng: Tính toán trực tiếp $a^b$ bằng phép nhân lặp $b$ lần và áp dụng phép $\pmod c$ sau mỗi lần nhân để tránh tràn số.

* Độ phức tạp thời gian: $O(b)$.
  * Cải tiến: Không cần thiết trong subtask này vì $b$ nhỏ ($\le 10^3$).

```cpp
#include <iostream>
using namespace std;

// Hằng số modulo
const long long MOD = 1e9 + 7;

void solve_subtask1() {
    long long a, b;
    cin >> a >> b;

if (b == 0) {
        cout << 1 << endl;
        return;
    }

long long result = 1;
    // Lấy a % MOD ngay từ đầu để giữ giá trị nhỏ
    long long base = a % MOD;

// Nhân lặp b lần
    for (int i = 0; i < b; ++i) {
        // Áp dụng tính chất (x * y) % c = ((x % c) * (y % c)) % c
        result = (result * base) % MOD;
    }
    cout << result << endl;
}
```

-----

### Subtask 2 & 3: $a, b \le 10^9$ (Lời giải tổng quát)

**Phân tích và Cải tiến:**
Các subtask 2 và 3 có số mũ $b$ lên tới $10^9$. Phương pháp lặp $O(b)$ của Subtask 1 sẽ không thể hoàn thành trong giới hạn thời gian (Time Limit Exceeded - TLE). Ta cần một thuật toán có độ phức tạp logarithmic.

Hướng cải tiến là sử dụng thuật toán **Lũy thừa nhị phân (Binary Exponentiation)**, dựa trên nguyên lý:

$a^b = \begin{cases} (a^{b/2})^2 & \text{nếu } b \text{ là số chẵn} \\ a \cdot (a^{(b-1)/2})^2 & \text{nếu } b \text{ là số lẻ} \end{cases}$

Thuật toán này giảm số phép nhân xuống còn $O(\log b)$.

* Độ phức tạp thời gian: $O(\log b)$.
  * Độ phức tạp không gian: $O(1)$.

```cpp
#include <iostream>
using namespace std;

// Hằng số modulo
const long long MOD = 1e9 + 7;

// Hàm tính lũy thừa nhị phân (a^b) % MOD
long long power(long long a, long long b, long long mod) {
    long long result = 1;
    // B1: Giữ cơ số nhỏ
    a %= mod;

while (b > 0) {
        // B2: Nếu b lẻ, nhân result với a hiện tại
        if (b % 2 == 1) {
            result = (result * a) % mod;
        }
        
        // B3: Bình phương cơ số (a^2, a^4, a^8, ...)
        a = (a * a) % mod; 
        
        // B4: Giảm b đi một nửa
        b /= 2;
    }
    return result;
}

void solve_subtask2_3() {
    long long a, b;
    cin >> a >> b;
    
    // Áp dụng thuật toán Lũy thừa nhị phân
    cout << power(a, b, MOD) << endl;
}
```

-----