Hướng dẫn giải của Số thứ n

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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, ngocnamhd03, kamiwama, tranhungss1702

Hiểu bài toán

Bài toán yêu cầu tính giá trị số thứ n (a_n) của một dãy số được định nghĩa quy nạp như sau:

a_0 = 1
Nếu i là số chẵn: ai = i * a{i-1}
Nếu i là số lẻ: ai = i + a{i-1} Với n trong khoảng từ 1 đến 100.

Ví dụ:

a_0 = 1
a1 (lẻ): 1 + a0 = 1 + 1 = 2
a2 (chẵn): 2 * a1 = 2 * 2 = 4
a3 (lẻ): 3 + a2 = 3 + 4 = 7
a4 (chẵn): 4 * a3 = 4 * 7 = 28 ...

Do giá trị tăng trưởng rất nhanh (đặc biệt với phép nhân), kết quả có thể vượt qua giới hạn của kiểu số nguyên 64-bit (long long) khi n lớn (ví dụ n=20 đã có thể vượt qua 2^63-1). Do đó, cần sử dụng kỹ thuật xử lý số lớn (Big Integer).

Các cách tiếp cận

Cách Mô phỏng trực tiếp với số lớn (Big Integer dạng chuỗi)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

// Hàm cộng hai số lớn dạng chuỗi
string cong(string a, string b) {
    string res = "";
    int carry = 0;
    int i = a.length() - 1;
    int j = b.length() - 1;

    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        res += (char)(sum % 10 + '0');
        carry = sum / 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

// Hàm nhân số lớn dạng chuỗi với một số nguyên nhỏ
string nhan(string a, int b) {
    string res = "";
    int carry = 0;
    for (int i = a.length() - 1; i >= 0; i--) {
        int prod = (a[i] - '0') * b + carry;
        res += (char)(prod % 10 + '0');
        carry = prod / 10;
    }
    while (carry) {
        res += (char)(carry % 10 + '0');
        carry /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    int n;
    cin >> n;

    string a = "1";

    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) {
            // i chẵn: nhân
            a = nhan(a, i);
        } else {
            // i lẻ: cộng
            a = cong(a, to_string(i));
        }
    }

    cout << a << endl;
    return 0;
}

Time Complexity: O(n * L), với L là độ dài số lớn (tại n=100, L ~ 100-150 chữ số)
Space Complexity: O(L)

Phương pháp này mô phỏng chính xác quy tắc tính toán của dãy số. Vì giá trị số rất lớn, ta lưu trữ a_i dưới dạng chuỗi ký tự (string).

Khởi tạo a = "1".
Duyệt i từ 1 đến n:
- Nếu i chẵn: gọi hàm nhân chuỗi a với số nguyên i.
- Nếu i lẻ: gọi hàm cộng chuỗi a với chuỗi đại diện cho i.
Các hàm cong và nhan hoạt động tương tự như cách tính toán thủ công trên giấy, xử lý các số có độ dài bất kỳ.

Cách Tối ưu hóa với Vector số nguyên (Big Integer dạng mảng)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Đại diện số lớn bằng vector, mỗi phần tử lưu 1 chữ số
// Vector lưu theo thứ tự ngược (units at index 0) để tiện cộng/trừ
struct BigInt {
    vector<int> digits;

    BigInt(int n = 0) {
        if (n == 0) digits.push_back(0);
        while (n > 0) {
            digits.push_back(n % 10);
            n /= 10;
        }
    }

    void add(int v) {
        int carry = v;
        for (int i = 0; i < digits.size(); i++) {
            if (carry == 0) break;
            int sum = digits[i] + carry;
            digits[i] = sum % 10;
            carry = sum / 10;
        }
        while (carry) {
            digits.push_back(carry % 10);
            carry /= 10;
        }
    }

    void multiply(int v) {
        int carry = 0;
        for (int i = 0; i < digits.size(); i++) {
            int prod = digits[i] * v + carry;
            digits[i] = prod % 10;
            carry = prod / 10;
        }
        while (carry) {
            digits.push_back(carry % 10);
            carry /= 10;
        }
    }

    void print() {
        for (int i = digits.size() - 1; i >= 0; i--) {
            cout << digits[i];
        }
        cout << endl;
    }
};

int main() {
    int n;
    cin >> n;

    BigInt a(1);

    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) {
            a.multiply(i);
        } else {
            a.add(i);
        }
    }

    a.print();
    return 0;
}

Time Complexity: O(n * L)
Space Complexity: O(L)

Thay vì dùng string, ta dùng vector để lưu các chữ số. Phương pháp này có ưu điểm:

Truy cập và thao tác với số nguyên trong vector thường nhanh hơn thao tác với chuỗi ký tự.
Dễ dàng mở rộng (resizable) khi số lượng chữ số tăng lên.
Logic xử lý tương tự: duyệt từ 1 đến n, thực hiện nhân hoặc cộng dựa trên tính chẵn lẻ của i. Vector lưu ngược (units at index 0) giúp việc thêm số dư (carry) vào cuối (đầu số) dễ dàng hơn.

Cách Sử dụng thư viện chuẩn (C++ BigInt)

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using namespace boost::multiprecision;

int main() {
    int n;
    cin >> n;

    cpp_int a = 1;

    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) {
            a *= i;
        } else {
            a += i;
        }
    }

    cout << a << endl;
    return 0;
}

Time Complexity: O(n * L)
Space Complexity: O(L)

Đây là giải pháp hiện đại nhất nếu môi trường lập trình hỗ trợ thư viện số lớn (như Boost.Multiprecision trong C++). Tuy nhiên, trong các kỳ thi lập trình thi đấu thông thường (Codeforces, VNOJ, ...), thư viện này thường không được kích hoạt. Nếu dùng C++11 hoặc muỗn code 'thuần', ta có thể dùng __int128 cho n nhỏ (n<40), nhưng với n=100 thì vẫn cần Big Integer.

Giải pháp này tối ưu nhất về thời gian cài đặt nhưng kém tính phổ biến trong các contest không hỗ trợ thư viện mở rộng. Trong code mẫu trên, giả định thư viện Boost được hỗ trợ (thường dùng trong các môi trường nghiên cứu hoặc lập trình viên tự setup).

Phân tích độ phức tạp

Cách tiếp cận	Time	Space	Tên
1	O(n * L), với L là độ dài số lớn (tại n=100, L ~ 100-150 chữ số)	O(L)	Mô phỏng trực tiếp với số lớn (Big Integer dạng chuỗi)
2	O(n * L)	O(L)	Tối ưu hóa với Vector số nguyên (Big Integer dạng mảng)
3	O(n * L)	O(L)	Sử dụng thư viện chuẩn (C++ BigInt)

Bài học kinh nghiệm

Xác định giới hạn của kiểu dữ liệu số nguyên (long long) để tránh tràn số (overflow). Với n=100, kết quả có hàng trăm chữ số.
Phép nhân là tác nhân gây tăng trưởng nhanh nhất (tích số lớn với số lớn, hoặc số lớn với số lớn dần).

Lỗi thường gặp

Giả sử int hoặc long long là đủ để lưu trữ kết quả.
Lỗi logic trong các hàm cộng/nhan số lớn (ví dụ: quên xử lý số dư cuối cùng).
Xử lý số 0 không đúng cách (ví dụ: in ra "00" thay vì "0").

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.