Dương lẻ

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp Tìm quy luật

Đề bài

Cho số nguyên $x$. Hãy tính tổng các số nguyên dương, lẻ và nhỏ hơn $x$ (không tính $x$).

Dữ liệu vào:

Một số nguyên $x$.

Kết quả:

Tổng các số nguyên dương lẻ nhỏ hơn $x$. Nếu không có số nào thì in ra $0$.

Giới hạn:

• $0 \le x \le 2 \cdot 10^9$

Subtask:

• Subtask 1 (40% số điểm): $x \le 10^6$.
• Subtask 2 (60% số điểm): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

6

Ví dụ 1 – output

9

Ví dụ 2 – input

37

Ví dụ 2 – output

324

• Ví dụ 1: các số dương lẻ nhỏ hơn $6$ là $1, 3, 5$; tổng bằng $9$.
• Ví dụ 2: $1 + 3 + 5 + \ldots + 35 = 324$ (không tính $37$ vì đề yêu cầu nhỏ hơn $x$).

Nguồn: phỏng theo bài "DƯƠNG LẺ" – vinhdinhcoder.net (chủ đề Lặp FOR).

Lời mở đầu

Cộng các số lẻ $1 + 3 + 5 + \ldots$ nhỏ hơn $x$ – một vòng lặp là xong? Đúng với $x \le 10^6$ (subtask 1). Nhưng $x$ lên tới $2 \cdot 10^9$ thì vòng lặp phải chạy cả tỉ lần, và tổng lên tới $10^{18}$. Bài này mình đi từ vòng lặp, rồi quan sát kết quả để tìm ra một quy luật rất đẹp: tổng $k$ số lẻ đầu tiên bằng $k^2$. Ghi chú: đề gốc là bài vòng lặp nhưng giới hạn $x \le 2 \cdot 10^9$ khiến vòng lặp quá chậm, nên mình chia subtask: $x \le 10^6$ (40%) cho vòng lặp, phần còn lại cần công thức.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngk số lẻ → k²Lời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Test 1–8 thuộc subtask 1 ($x \le 10^6$), test 9–20 có $x$ tới $2 \cdot 10^9$.

Test	Nội dung kiểm tra
1–8	Ví dụ đề, $x = 0, 1, 2, 3$ (chưa có hoặc chỉ có số 1), $x$ lẻ và chẵn cỡ $10^6$
9–10, 20	$x = 92\,683, 92\,684, 92\,681$: ngay quanh chỗ $k^2$ vượt giới hạn int
11–19	$x$ tới $2 \cdot 10^9$, chẵn và lẻ: tổng tới $10^{18}$, vòng lặp từng số bị quá thời gian

Ý tưởngTừ vòng lặp đến quy luật k²

Cách 1 – vòng lặp (subtask 1). Cho i chạy $1, 3, 5, \ldots$ (nhảy 2 bước) chừng nào $i < x$, cộng dồn vào s:

long long s = 0;
for(long long i = 1; i < x; i += 2) s += i;

Chú ý dấu < (không phải <=): đề nói nhỏ hơn $x$, nên với $x = 37$ ta không cộng 37.

Cách 2 – quan sát. Viết ra vài tổng đầu tiên: $1 = 1^2$, $1 + 3 = 4 = 2^2$, $1 + 3 + 5 = 9 = 3^2$, $1 + 3 + 5 + 7 = 16 = 4^2$… Tổng $k$ số lẻ đầu tiên luôn bằng $k^2$! (Hình dung: hình vuông $k \times k$ ô, thêm một "viền chữ L" gồm $2k + 1$ ô thì thành hình vuông $(k + 1) \times (k + 1)$.)

Các số lẻ dương nhỏ hơn $x$ là $1, 3, \ldots$ – có đúng $k = x / 2$ số (chia nguyên): $x = 6$ có 3 số ($1, 3, 5$), $x = 7$ cũng chỉ 3 số, $x = 37$ có 18 số. Vậy đáp án là $k \cdot k$ với $k = x / 2$: ví dụ $37 / 2 = 18$, $18^2 = 324$ ✓.

Chọn kiểu dữ liệu

$k$ tới $10^9$ nên $k \cdot k$ tới $10^{18}$ → k phải là long long. Nếu k là int thì k * k tràn ngay khi $k > 46\,340$, kể cả khi gán kết quả vào biến long long.

Em nhập $x$ rồi bấm Tiếp để xem vòng lặp cộng từng số lẻ – để ý cột tổng luôn bằng cột $k \cdot k$:

x =

Ví dụ nhanh:

Lời giảiĐếm số lẻ rồi bình phương

Lời giải đầy đủ chỉ gồm hai phép tính, mọi biến là long long. (Vòng lặp ở phần ý tưởng vẫn được đủ điểm subtask 1.)

C++▶ Chạy tay từng dòng codeCó k = x / 2 số lẻ dương nhỏ hơn x, tổng của chúng là k * k.

Dữ liệu vào (stdin) – sửa thoải mái6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Phép chia x / 2 giữa hai số nguyên là chia nguyên: $7 / 2 = 3$ – đúng bằng số số lẻ dương nhỏ hơn 7 ($1, 3, 5$).
2. Vòng lặp nhảy 2 bước ở phần ý tưởng phải chạy tới $10^9$ lần khi $x = 2 \cdot 10^9$: trong C++ có thể vẫn kịp nhờ trình biên dịch tối ưu, nhưng viết kiểu duyệt từng số rồi kiểm tra lẻ, hoặc viết bằng Python, thì chắc chắn quá thời gian (xem phần bẫy).
3. Python không lo tràn số, nhưng vẫn cần công thức để chạy kịp.

Không gian$O(1)$

Thời gian$O(1)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.004s. Bản Python đúng 20/20 test, chạy lâu nhất 0.038s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Hiểu nhầm "nhỏ hơn hoặc bằng" $x$ (cộng cả $x$ khi $x$ lẻ)	8/20	sai test 2, 4, 6, 7, 9, 12, 14, 15, 16, 17, 18, 20
Khai báo int k rồi gán long long s = k * k	7/20	sai test 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
Vòng lặp với tổng kiểu int	7/20	sai test 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
Duyệt từng số từ 1 tới $x - 1$, kiểm tra lẻ (long long)	12/20	sai test 11, 12, 13, 14, 15, 16, 17, 19
Python: vòng lặp range(1, x, 2)	11/20	sai test 11, 12, 13, 14, 15, 16, 17, 18, 19

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.004s	Full điểm
	Python	20/20	0.038s	Full điểm
Nhầm ≤ x	C++	8/20	–	Mất 12 test
int k	C++	7/20	–	Mất 13 test
Tổng int	C++	7/20	–	Mất 13 test
Duyệt từng số	C++	12/20	–	Mất 8 test
Python vòng lặp	C++	11/20	–	Mất 9 test

Ghi chú của mình: khi vòng lặp quá chậm, hãy in thử kết quả với vài giá trị nhỏ ($1, 4, 9, 16, \ldots$) – quy luật thường hiện ra ngay trước mắt.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇