Tóm tắt đề

Cho số nguyên $n$. Tính tổng các số chẵn / lẻ từ 1 đến $n$.

Giới hạn đề bài

• Subtask 1: Có 60% số test: $1\le n\le {10}^6$.
• Subtask 2: Có 40% số test: ${10}^6<n\le {10}^9.$

Lời giải

Subtask 1: $1\le n\le {10}^6.$

Tiếp cận

Sử dụng vòng lặp for để tính tổng.

Thực hiện

Đối với $n$ chẵn thực hiện vòng for từ 2 đến $n$ kết hợp bước nhảy 2 để tính kết quả. Đối với $n$ lẻ thực hiện vòng for từ 1 đến $n$ kết hợp bước nhảy 2 để tính kết quả.

Độ phức tạp

$O(n/2).$

Subtask 2: ${10}^6<n\le {10}^9$

Kiến thức liên quan

Một dãy được gọi là dãy cấp số cộng khi dãy có dạng:

$a,a+d,a+2d,a+3d,...,a+(k-1)d$. Trong đó: * Hạng đầu là $a$. * Công sai là $d$. * Số lượng số hạng là $k$. Gọi $l$ là số cuối cùng của dãy thì ta có: $k=\frac{l-a}{d}+1$. Tổng của $k$ số hạng đầu tiên được tính theo công thức: $S=\frac{k}{2}·(a+l)$. #### Tiếp cận Nhận thấy tổng cần tìm là 1 dãy cấp số cộng có công sai là 2. Nên ta có thể áp dụng các công thức của cấp số cộng. #### Thực hiện Áp dụng công thức cho số nguyên $n$ tùy theo dạng chẵn lẻ. #### Độ phức tạp $O(1).$