Hướng dẫn giải của Tính lũy thừa 2
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tính giá trị của a^n với a là số nguyên dương (1 ≤ a ≤ 10^9) và n là số nguyên dương (1 ≤ n ≤ 1000). Kết quả có thể rất lớn và vượt quá khả năng lưu trữ của các kiểu dữ liệu nguyên tiêu chuẩn (như long long). Do đó, cần sử dụng các kỹ thuật đặc biệt như tính toán dạng chuỗi số học hoặc sử dụng thư viện Big Integer.
Các cách tiếp cận
Cách Nhân chuỗi (String Multiplication)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// Hàm nhân số lớn dạng chuỗi
char* multiply_strings(const char* num1, const char* num2) {
int len1 = strlen(num1);
int len2 = strlen(num2);
// Kết quả có thể có độ dài tối đa là len1 + len2
int* result = (int*)calloc(len1 + len2, sizeof(int));
// Đảo chuỗi để tính toán từ chữ số cuối (đơn vị)
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
int mul = (num1[len1 - 1 - i] - '0') * (num2[len2 - 1 - j] - '0');
int sum = mul + result[i + j];
result[i + j] = sum % 10;
result[i + j + 1] += sum / 10;
}
}
// Xóa số 0 ở đầu
int len = len1 + len2;
while (len > 1 && result[len - 1] == 0) len--;
char* final_res = (char*)malloc(len + 1);
for (int i = 0; i < len; i++) {
final_res[len - 1 - i] = result[i] + '0';
}
final_res[len] = '\0';
free(result);
return final_res;
}
int main() {
char a_str[100];
int n;
scanf("%s %d", a_str, &n);
char* current = (char*)malloc(strlen(a_str) + 1);
strcpy(current, a_str);
char* next;
for (int i = 1; i < n; i++) {
next = multiply_strings(current, a_str);
free(current);
current = next;
}
printf("%s\n", current);
free(current);
return 0;
}
- Time Complexity: O(n * M^2) hoặc O(n * M * log M) tùy thuật toán nhân. Trong đó M là số lượng chữ số của a^n (có thể lên tới ~1000 * log10(10^9) ≈ 3000 chữ số). Với n=1000, phương pháp này vẫn chạy nhanh.
- Space Complexity: O(M) để lưu trữ kết quả trung gian.
Phương pháp này mô phỏng phép nhân như cách tính trên giấy. Thay vì lưu trữ số nguyên, ta lưu số dưới dạng chuỗi ký tự. Với mỗi bước lũy thừa, ta thực hiện nhân chuỗi số hiện tại với số cơ sở a. Ta cần một hàm nhân hai chuỗi số để thực hiện phép tính này. Kỹ thuật thường là tạo một mảng các số nguyên để lưu các tích trung gian, xử lý nhớ, rồi chuyển lại thành chuỗi.
Cách Mảng số nguyên (Integer Array Simulation)
#include <stdio.h>
#include <string.h>
#define MAX_DIGITS 3000 // Đủ để lưu 1000^1000 (khoảng 3000 chữ số)
void luythua(int a, int n) {
int res[MAX_DIGITS];
memset(res, 0, sizeof(res));
res[0] = 1; // Khởi tạo kết quả bằng 1
int len = 1; // Độ dài số hiện tại
for (int i = 0; i < n; i++) {
int carry = 0;
for (int j = 0; j < len; j++) {
int prod = res[j] * a + carry;
res[j] = prod % 10;
carry = prod / 10;
}
while (carry) {
res[len] = carry % 10;
carry /= 10;
len++;
}
}
for (int i = len - 1; i >= 0; i--) {
printf("%d", res[i]);
}
}
int main() {
int a, n;
scanf("%d %d", &a, &n);
luythua(a, n);
return 0;
}
- Time Complexity: O(n * len), với len là số chữ số của kết quả. Tối đa khoảng O(1000 * 3000) thao tác.
- Space Complexity: O(MAX_DIGITS) ~ O(3000).
Thay vì dùng chuỗi, ta dùng mảng số nguyên res[] để lưu các chữ số của kết quả, res[0] là số hàng đơn vị. Với mỗi lần nhân, ta nhân toàn bộ mảng hiện tại với số a và xử lý số nhớ (carry). Phương pháp này hiệu quả về mặt bộ nhớ và tốc độ so với việc thao tác với chuỗi ký tự.
Cách Đệ quy chia đôi (Exponentiation by Squaring)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// Hàm cộng hai số lớn dạng chuỗi
string add(string n1, string n2) {
string sum = "";
int i = n1.length() - 1;
int j = n2.length() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry) {
int digit1 = (i >= 0) ? n1[i--] - '0' : 0;
int digit2 = (j >= 0) ? n2[j--] - '0' : 0;
int currentSum = digit1 + digit2 + carry;
sum += (char)(currentSum % 10 + '0');
carry = currentSum / 10;
}
reverse(sum.begin(), sum.end());
return sum;
}
// Hàm nhân hai số lớn dạng chuỗi
string multiply(string n1, string n2) {
int len1 = n1.size();
int len2 = n2.size();
if (len1 == 0 || len2 == 0 || n1 == "0" || n2 == "0") return "0";
vector<int> result(len1 + len2, 0);
int i_n1 = 0;
for (int i = len1 - 1; i >= 0; i--) {
int carry = 0;
int n1_digit = n1[i] - '0';
int i_n2 = 0;
for (int j = len2 - 1; j >= 0; j--) {
int n2_digit = n2[j] - '0';
int sum = n1_digit * n2_digit + result[i_n1 + i_n2] + carry;
carry = sum / 10;
result[i_n1 + i_n2] = sum % 10;
i_n2++;
}
if (carry > 0)
result[i_n1 + i_n2] += carry;
i_n1++;
}
int i = result.size() - 1;
while (i >= 0 && result[i] == 0) i--;
if (i < 0) return "0";
string s = "";
while (i >= 0) s += std::to_string(result[i--]);
return s;
}
// Hàm lũy thừa chia đôi
string power(string a, int n) {
if (n == 0) return "1";
if (n == 1) return a;
string temp = power(a, n / 2);
if (n % 2 == 0)
return multiply(temp, temp);
else
return multiply(multiply(temp, temp), a);
}
int main() {
long long a_int;
int n;
cin >> a_int >> n;
string a = to_string(a_int);
cout << power(a, n) << endl;
return 0;
}
- Time Complexity: O(log n * M^2) hoặc O(log n * M log M). Số lần nhân giảm từ n xuống log n.
- Space Complexity: O(M).
Phương pháp này tối ưu hóa số lượng phép nhân. Thay vì nhân n lần, ta dùng tính chất a^n = (a^(n/2))^2. Nếu n chẵn, ta chỉ cần nhân kết quả của nửa sau với chính nó. Nếu n lẻ, nhân thêm một lần a. Số lượng phép nhân cần thiết giảm từ O(n) xuống O(log n). Tuy nhiên, mỗi phép nhân vẫn là nhân số lớn (dùng chuỗi).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n * M^2) hoặc O(n * M * log M) tùy thuật toán nhân. Trong đó M là số lượng chữ số của a^n (có thể lên tới ~1000 * log10(10^9) ≈ 3000 chữ số). Với n=1000, phương pháp này vẫn chạy nhanh. | O(M) để lưu trữ kết quả trung gian. | Nhân chuỗi (String Multiplication) |
| 2 | O(n * len), với len là số chữ số của kết quả. Tối đa khoảng O(1000 * 3000) thao tác. | O(MAX_DIGITS) ~ O(3000). | Mảng số nguyên (Integer Array Simulation) |
| 3 | O(log n * M^2) hoặc O(log n * M log M). Số lần nhân giảm từ n xuống log n. | O(M). | Đệ quy chia đôi (Exponentiation by Squaring) |
Bài học kinh nghiệm
- Kiểu dữ liệu nguyên tiêu chuẩn (long long) không đủ lưu kết quả. Cần lưu trữ số dưới dạng chuỗi hoặc mảng.
- Phép nhân số lớn có thể được thực hiện mô phỏng theo cách tính trên giấy, sử dụng mảng lưu trữ trung gian.
- Giảm số lượng phép nhân bằng cách sử dụng phương pháp chia đôi (Exponentiation by Squaring) giúp tăng tốc độ đáng kể.
Lỗi thường gặp
- Quên kiểm tra số 0 ở đầu khi in kết quả từ mảng.
- Xử lý nhầm số nhớ (carry) khi thực hiện phép nhân hoặc cộng.
- Sử dụng đệ quy quá sâu (nếu n rất lớn) gây tràn stack, nhưng với n ≤ 1000 thì đệ quy chia đôi an toàn.
Bình luận