Hiểu bài toán

Bài toán yêu cầu tìm số Y là số có chữ số cuối cùng bằng tổng bình phương của các số từ 1 đến n. Cụ thể, Y = (1^2 + 2^2 + ... + n^2) mod 10. Ta cần in ra chữ số cuối cùng này (Y mod 10).

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

Cách Công thức toán học (Optimized)

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long x = (n + 1) % 10;
    cout << (x * x) % 10;
    return 0;
}

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

Áp dụng công thức tổng bình phương: S = n(n+1)(2n+1)/6. Ta chỉ quan tâm đến chữ số cuối cùng (mod 10). Qua phân tích quy luật, ta thấy kết quả phụ thuộc trực tiếp vào (n+1) mod 10. Cụ thể, Y = ((n+1) mod 10)^2 mod 10. Ví dụ: nếu n = 5 thì (5+1) = 6, 6^2 = 36, chữ số cuối là 6. Code tính trực tiếp (n+1) % 10, bình phương rồi lấy phần dư cho 10.

Cách Tính trực tiếp theo công thức

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n; cin >> n;
    cout << ( ( (n + 1) % 10 ) * ( (n + 1) % 10 ) ) % 10;
}

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

Đây là cách viết gọn của phương pháp đầu tiên. Tính (n+1) % 10, nhân với chính nó rồi chia lấy dư cho 10. Cách này ngắn gọn nhưng có thể khó hiểu nếu không biết lý do tại sao lại chỉ cần mỗi (n+1) mod 10.

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

Bài học kinh nghiệm

• Bài toán chỉ yêu cầu chữ số cuối cùng nên có thể tối ưu bằng cách xét modulo 10 ở mỗi bước.
• Quy luật xuất hiện: (1^2 + ... + n^2) mod 10 = ((n+1) mod 10)^2 mod 10.

Lỗi thường gặp

• Nếu dùng vòng lặp để tính tổng bình phương với n lớn (ví dụ 10^18) sẽ bị TLE.
• Sai công thức công thức tổng bình phương nếu tính trực tiếp mà không chia 6 đúng cách trong phép chia nguyên.