Hiểu bài toán

Bài toán yêu cầu xác định tính chẵn/lẻ của tổng của N số nguyên liên tiếp bí mật. Tuy nhiên, thay vì thực hiện tính toán trực tiếp, ta cần phân tích tính chất của dãy số liên tiếp. Với N số nguyên liên tiếp bất kỳ, ta có thể mô tả chúng dưới dạng: a, a+1, a+2, ..., a+N-1. Tổng của chúng là: S = Na + (N-1)N/2. Để xác định xem S luôn chẵn, luôn lẻ, hay có thể là cả hai, ta cần xét tính chẵn lẻ của các thành phần trong công thức này. Tuy nhiên, có một quy luật đơn giản hơn dựa trên độ dài dãy số. Nếu N là số lẻ, ta có thể chọn dãy số toàn chẵn hoặc toàn lẻ (ví dụ: 1,2,3 hay 2,3,4) để tổng thay đổi tính chẵn lẻ, nên kết quả luôn là 2 (có thể chẵn hoặc lẻ). Nếu N là số chẵn, tổng của N số liên tiếp luôn có tính chẵn lẻ cố định: nếu N chia hết cho 4 thì tổng luôn chẵn, nếu N chia hết cho 2 nhưng không chia hết cho 4 thì tổng luôn lẻ.

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

Cách Phân tích tính chẵn lẻ của tổng

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

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

    if (n % 2 == 1) cout << 2 << endl;
    else if (n % 4 == 0) cout << 0 << endl;
    else cout << 1 << endl; 

    return 0;
}

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

Đây là cách tiếp cận trực tiếp dựa trên quy luật toán học.

1. Nếu N là số lẻ (N % 2 == 1): Dãy có thể là 1, 2, ..., N (tổng lẻ) hoặc 2, 3, ..., N+1 (tổng chẵn tùy N). Thực tế, với N lẻ, ta luôn có thể tìm thấy một dãy tổng chẵn và một dãy tổng lẻ. Ví dụ: Consider 3 số: 1+2+3=6 (chẵn), 2+3+4=9 (lẻ). Do đó in ra 2.
2. Nếu N là số chẵn (N % 2 == 0): Tổng của N số liên tiếp có tính chẵn lẻ cố định.
   • Nếu N chia hết cho 4 (N % 4 == 0): Tổng luôn chẵn. Ví dụ N=4: 1+2+3+4=10 (chẵn), 2+3+4+5=14 (chẵn). In ra 0.
   • Nếu N chia hết cho 2 nhưng không chia hết cho 4 (N % 4 != 0): Tổng luôn lẻ. Ví dụ N=2: 1+2=3 (lẻ). N=6: 1+2+3+4+5+6=21 (lẻ). In ra 1. Cách này tối ưu nhất về cả thời gian và bộ nhớ.

Cách Cách tiếp cận dựa trên phép chia đôi

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N;
    cin >> N;

    if (N % 2 == 1) {
        cout << 2;
    } else {
        long long k = N / 2;
        if (k % 2 == 0) cout << 0;
        else cout << 1;
    }
    return 0;
}

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

Cách này cũng dựa trên cùng một tiên đề toán học nhưng biến đổi logic một chút.

• Nếu N là số lẻ, kết quả là 2 (giống cách 1).
• Nếu N là số chẵn, ta xét N/2.
  • Nếu N chia hết cho 4 thì N/2 là số chẵn (k % 2 == 0) -> Tổng chẵn (in 0).
  • Nếu N không chia hết cho 4 (nghĩa là N/2 là số lẻ) -> Tổng lẻ (in 1). Điều này tương đương hoàn toàn với cách 1 nhưng thông qua một phép biến đổi số học.

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

Bài học kinh nghiệm

• Bài toán không cần xử lý mảng hay số thực, chỉ cần logic chẵn lẻ dựa trên N.
• Tổng của N số liên tiếp có tính chẵn lẻ xác định: 'Luôn chẵn' nếu N chia hết cho 4, 'Luôn lẻ' nếu N chia hết cho 2 mà không chia hết cho 4, và 'Khả định cả 2' nếu N lẻ.

Lỗi thường gặp

• Lỗi tràn số kiểu dữ liệu (Integer Overflow): N có giá trị lên tới 10^18, bắt buộc phải sử dụng long long (C++) hoặc long (Java).
• Lỗi logic so sánh: Viết điều kiện if (N % 2 == 0) rồi mới kiểm tra chia hết cho 4, hoặc viết nhầm else if (N == 0) thay vì kiểm tra chia hết.