Hiểu bài toán

Bài toán yêu cầu tính tổng của n số lẻ đầu tiên, bắt đầu từ 1 (tức là 1 + 3 + 5 + ... + (2n-1)). Với n rất lớn (lên đến 10^30), không thể tính trực tiếp. Tuy nhiên, có một công thức toán học quen thuộc: tổng của n số lẻ đầu tiên bằng n^2. Do đó, bài toán này thực chất là yêu cầu tính n^2 và lấy kết quả modulo 10^6 + 7. Input là một chuỗi số rất dài biểu diễn cho n, do đó cần xử lý chuỗi để tính n modulo 10^6 + 7 trước khi bình phương.

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

Cách Xử lý chuỗi và tính toán theo công thức n^2

#include <iostream>
#include <string>
using namespace std;

const int MOD = 1e6 + 7;

int main() {
    string s;
    cin >> s;
    long long num = 0;
    for (char c : s) {
        num = (num * 10 + (c - '0')) % MOD;
    }
    long long result = (num * num) % MOD;
    cout << result << endl;
    return 0;
}

• Time Complexity: O(L), trong đó L là độ dài chuỗi n
• Space Complexity: O(1)

Phương pháp này dựa trên nhận thức toán học rằng tổng của n số lẻ đầu tiên bằng n^2. Vì n quá lớn để lưu trữ trong kiểu dữ liệu số nguyên chuẩn, ta xử lý input dưới dạng chuỗi. Ta duyệt qua từng ký tự của chuỗi, cập nhật giá trị của n theo mô-đun của MOD (10^6 + 7) tại mỗi bước. Sau khi có giá trị n % MOD, ta chỉ cần bình phương giá trị này và lấy modulo một lần nữa để ra kết quả cuối cùng. Đây là cách tiếp cận trực tiếp và hiệu quả nhất.

Cách Xử lý chuỗi bằng stringstream

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

const long long MOD = 1000007;

int main() {
    string n_str;
    cin >> n_str;

    long long n_mod = 0;
    for (char c : n_str) {
        n_mod = (n_mod * 10 + (c - '0')) % MOD;
    }

    long long result = (n_mod * n_mod) % MOD;

    cout << result << endl;

    return 0;
}

• Time Complexity: O(L)
• Space Complexity: O(1)

Đây là biến thể của phương pháp đầu tiên, sử dụng các thư viện chuẩn như <sstream> (mặc dù trong code mẫu không dùng stringstream để parse số do số quá lớn, mà vẫn dùng vòng lặp duyệt chuỗi). Logic cơ bản giống hệt nhau: chuyển đổi chuỗi thành số nguyên dưới dạng modulo, rồi tính bình phương. Việc sử dụng stringstream để parse trực tiếp số lớn từ chuỗi sang long long là không khả thi vì số quá lớn, nên cách tiếp cận duyệt chuỗi vẫn là tối ưu.

Cách Brute Force (Không khả thi)

// Pseudocode for conceptual understanding
long long sum = 0;
for(int i = 1; i <= n; i++) {
    sum += (2*i - 1);
}
// Hoặc: for(int i=1; i<=2*n; i+=2) sum += i;

• Time Complexity: O(n) -> Quá chậm, n ~ 10^30
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất: dùng vòng lặp để cộng dồn từng số lẻ. Tuy nhiên, với ràng buộc n ≤ 10^30, độ phức tạp O(n) là hoàn toàn không thể chấp nhận được (vòng lặp sẽ chạy hàng tỷ năm). Các giải pháp đã nộp đều không sử dụng cách này vì nó vi phạm ràng buộc thời gian và không xử lý được số đầu vào quá lớn.

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

Bài học kinh nghiệm

• Bài toán có mối quan hệ toán học trực tiếp: tổng n số lẻ đầu tiên = n^2. Nhận ra điều này giúp giảm bài toán về một phép tính bình phương đơn giản.
• Vì n rất lớn (vượt quá khả năng lưu trữ của long long), ta phải xử lý chuỗi đầu vào. Ta có thể tính giá trị n modulo M ngay trong quá trình đọc chuỗi bằng công thức: num = (num * 10 + digit) % MOD.
• Phép tính (a * b) % MOD có thể được tối ưu bằng cách dùng long long để tránh tràn số nếu a và b nhỏ hơn sqrt(LLONG_MAX). Trong bài này, MOD là 10^6+7, nên n_mod < MOD, và n_mod * n_mod nhỏ hơn 10^12, vừa với long long (khoảng 9x10^18).

Lỗi thường gặp

• Cố gắng lưu n vào kiểu int hoặc long long trực tiếp từ input会导致 overflow ngay lập tức vì n có thể lên tới 10^30.
• Quên lấy modulo sau mỗi bước tính toán khi duyệt chuỗi, dẫn đến tràn số biến num.
• Sai công thức tính tổng các số lẻ (ví dụ: nhầm sang công thức tổng các số tự nhiên n(n+1)/2).