Elearning CodePath – CTP Online Judge

Hai Chữ Số Tận Cùng của 7^N

LAST2

🟢 Hard #Math #Number Theory

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho một số nguyên $N$.
Yêu cầu: Hãy đưa ra hai chữ số tận cùng của $7^N$.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `LAST2.INP`:

* Một dòng chứa số nguyên $N$.

Giới hạn:
* $0 \le N \le 10^9$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `LAST2.OUT` một số nguyên duy nhất là hai chữ số tận cùng của $7^N$. Kết quả phải có hai chữ số (ví dụ: $07$ nếu kết quả là $7$).

---
### ✨ Ví dụ

| Input | Output | Giải thích |
| :--- | :--- | :--- |
| `1` | `07` | $7^1 = 7$. Hai chữ số tận cùng là $07$. |
| `2` | `49` | $7^2 = 49$. Hai chữ số tận cùng là $49$. |
| `3` | `43` | $7^3 = 343$. Hai chữ số tận cùng là $43$. |
| `4` | `01` | $7^4 = 2401$. Hai chữ số tận cùng là $01$. |
| `5` | `07` | $7^5 = 16807$. Hai chữ số tận cùng là $07$. |

---
### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $0 \le N \le 20$ | $30\%$ |
| 2 | $0 \le N \le 1000$ | $30\%$ |
| 3 | $0 \le N \le 10^9$ | $40\%$ |

---

✅ Đã AC: 0 / 7 submissions

📘 Lời giải

# 💡 Lời giải Bài toán Hai Chữ Số Tận Cùng của $7^N$

Bài toán yêu cầu tìm hai chữ số tận cùng của $7^N$, tức là tính $7^N \pmod{100}$. Đây là bài toán áp dụng tính chất **chu kỳ** của lũy thừa $\pmod{100}$.

### 🔑 Phân tích Chu kỳ

Chu kỳ của $7^N \pmod{100}$ được xác định bởi định lý Euler's Totient.
Ta cần tính $\lambda(100)$, hàm Carmichael của $100$:

$\lambda(100) = \text{lcm}(\lambda(4), \lambda(25))$

Trong đó:

* $\lambda(4) = 2$ (Chu kỳ: $7^1 \equiv 3$, $7^2 \equiv 1 \pmod 4$)
  * $\lambda(25) = \phi(25) = 25(1 - 1/5) = 20$ (Chu kỳ $\pmod{25}$)

$\lambda(100) = \text{lcm}(2, 20) = 20$

Chu kỳ của $7^N \pmod{100}$ là $20$. Do đó, ta chỉ cần rút gọn số mũ $N$ về số mũ hiệu quả $N_{\text{eff}}$:

$N_{\text{eff}} = \begin{cases} 20 & \text{nếu } N \pmod{20} = 0 \text{ và } N > 0 \\ N \pmod{20} & \text{nếu } N \pmod{20} \ne 0 \\ 0 & \text{nếu } N = 0 \end{cases}$

Kết quả là $7^{N_{\text{eff}}} \pmod{100}$.

### Subtask 1: $0 \le N \le 20$

Ý tưởng: Tính toán trực tiếp bằng phép nhân lặp $N$ lần.

* Độ phức tạp thời gian: $O(N)$.
  * Cải tiến: Thuật toán này đủ nhanh vì $N \le 20$.

```cpp
// Hàm tính lũy thừa lặp cho N nhỏ
long long power_lap(long long n) {
    if (n == 0) return 1;
    long long res = 1;
    for (int i = 0; i < n; ++i) {
        res = (res * 7) % 100;
    }
    return res;
}
```

-----

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

**Phân tích và Cải tiến:**
Số mũ $N$ lớn ($10^9$) yêu cầu phải sử dụng cả **tính chất chu kỳ** và **Lũy thừa nhị phân (Binary Exponentiation)**.

1.  **Rút gọn số mũ:** Giảm $N \to N_{\text{eff}} \le 20$ bằng phép $\pmod{20}$.
2.  **Tính lũy thừa:** Tính $7^{N_{\text{eff}}} \pmod{100}$ bằng Lũy thừa nhị phân (hoặc có thể dùng lặp vì $N_{\text{eff}}$ rất nhỏ).

* Độ phức tạp thời gian: $O(\log N_{\text{eff}}) = O(1)$ (vì $N_{\text{eff}} \le 20$ là hằng số).
  * Độ phức tạp không gian: $O(1)$.

```cpp
#include <iostream>
#include <iomanip> // Dùng cho setw và setfill

using namespace std;

// Hàm tính lũy thừa nhị phân: (base^exp) % mod
long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod; 
    
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod; 
        exp /= 2;
    }
    return result;
}

void solve_general() {
    long long N; 
    cin >> N;

// 1. Trường hợp đặc biệt N = 0
    if (N == 0) {
        cout << "01" << endl;
        return;
    }

// 2. Rút gọn số mũ N_eff = N mod 20
    long long N_eff = N % 20;

// Nếu N mod 20 = 0 (và N > 0), ta lấy N_eff = 20 (cuối chu kỳ)
    if (N_eff == 0) {
        N_eff = 20;
    }

// 3. Tính 7^(N_eff) mod 100
    long long result = power(7, N_eff, 100);
    
    // 4. Định dạng output thành 2 chữ số (ví dụ: 7 -> 07)
    // setw(2): đảm bảo chiều rộng 2 ký tự
    // setfill('0'): điền ký tự '0' vào chỗ trống
    cout << setfill('0') << setw(2) << result << endl;
}

int main() {
    // Tăng tốc độ I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

solve_general();

return 0;
}
```