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\le10^{6}$.
• Subtask 2: Có 40% số test: $10^{6}<n\le10^{9}.$</li>

Lời giải

Subtask 1: $1\le n\le10^{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\le10^{9}$</h5>

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}\cdot(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).$