Hoàn hảo

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp for Ước số

Đề bài

Một số nguyên dương được gọi là số hoàn hảo nếu tổng các ước nhỏ hơn nó bằng chính nó. Ví dụ $28$ là số hoàn hảo vì các ước nhỏ hơn 28 của nó là $1, 2, 4, 7, 14$ và $1 + 2 + 4 + 7 + 14 = 28$.

Cho số nguyên dương $n$, hãy kiểm tra $n$ có phải là số hoàn hảo hay không.

Dữ liệu vào:

Một số nguyên dương $n$.

Kết quả:

In ra YES nếu $n$ là số hoàn hảo, ngược lại in ra NO.

Giới hạn:

• $2 \le n \le 10^7$

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

28

Ví dụ 1 – output

YES

Ví dụ 2 – input

29

Ví dụ 2 – output

NO

• Ví dụ 1: $1 + 2 + 4 + 7 + 14 = 28$ nên 28 là số hoàn hảo.
• Ví dụ 2: 29 là số nguyên tố, ước nhỏ hơn nó chỉ có $1$, mà $1 \ne 29$.

Nguồn: phỏng theo bài "HOÀN HẢO" – vinhdinhcoder.net (chủ đề Lặp FOR).

Lời mở đầu

Kiểm tra số hoàn hảo cần tính tổng các ước nhỏ hơn $n$. Cách dễ nghĩ nhất là thử mọi số từ 1 tới $n - 1$, nhưng mình sẽ chỉ cho em mẹo chỉ duyệt tới $\sqrt{n}$ – nhanh hơn hàng nghìn lần – và cái bẫy cộng trùng ước ở số chính phương.

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ưởngduyệt tới √nLờ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. Mọi test có $2 \le n \le 10^7$. Trong khoảng này chỉ có 4 số hoàn hảo: $6, 28, 496, 8128$ – cả bốn đều có trong bộ test.

Test	Nội dung kiểm tra
1, 3, 8, 13	Các số hoàn hảo $28, 6, 496, 8128$ (đáp án YES)
2, 9, 10, 14, 15	Các số "hàng xóm" của số hoàn hảo: $29, 495, 497, 8127, 8129$
4–7, 16, 20	$n = 2$ (nhỏ nhất), $3$, $12$ (tổng ước lớn hơn $n$), $27$, $2^{12} = 4096$ và $2^{10} \cdot 8191$
11, 12, 19	Số chính phương $16, 36, 3162^2 = 9\,998\,244$ (bẫy cộng căn hai lần)
17, 18	Số nguyên tố lớn $9\,999\,991$ và $n = 10^7$

Ý tưởngƯớc đi theo cặp: i và n / i

Nếu $i$ là ước của $n$ thì $n / i$ cũng là ước. Hai ước trong một cặp có một số $\le \sqrt{n}$ và một số $\ge \sqrt{n}$. Vậy chỉ cần cho $i$ chạy từ $1$ khi $i \cdot i \le n$: mỗi lần $n$ chia hết cho $i$ thì cộng cả $i$ lẫn $n / i$.

• Với $n = 28$: các cặp là $(1, 28)$, $(2, 14)$, $(4, 7)$ → tổng mọi ước là $56$.
• Bỏ chính $n$ ra (nó nằm trong cặp $(1, n)$): $56 - 28 = 28 = n$ → YES.

Bẫy số chính phương

Với $n = 36$, cặp $(6, 6)$ có hai số trùng nhau – chỉ được cộng $6$ một lần. Vì thế khi cộng n / i phải kiểm tra n / i != i.

Vòng lặp chỉ chạy khoảng $\sqrt{10^7} \approx 3163$ lần thay vì $10^7$ lần.

Em nhập $n$ rồi bấm Tiếp để xem các cặp ước được tìm ra:

n =

Ví dụ nhanh:

Lời giảiDuyệt i khi i * i <= n

Viết điều kiện i * i <= n thay cho i <= sqrt(n) để khỏi dùng số thực.

C++▶ Chạy tay từng dòng codeCộng các cặp ước i và n / i, rồi so sánh với n.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Cặp $(1, n)$ luôn được cộng ở vòng $i = 1$, nên sau vòng lặp trừ đi $n$ là được tổng các ước nhỏ hơn $n$.
2. Duyệt thẳng $i$ từ $1$ tới $n - 1$ cũng đúng và bản C++ vẫn kịp ($10^7$ phép chia), nhưng bản Python chạy khoảng 1 giây – rất dễ quá thời gian. Cách duyệt tới $\sqrt{n}$ chạy tức thì ở cả hai ngôn ngữ.
3. Tổng các ước của $n \le 10^7$ chưa tới $5 \cdot 10^7$, int vẫn đủ; mình dùng long long cho chắc.

Không gian$O(1)$

Thời gian$O(\sqrt{n})$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.003s. Bản Python đúng 20/20 test, chạy lâu nhất 0.037s. 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ú
Duyệt tới $\sqrt{n}$ nhưng quên bỏ chính $n$ ra khỏi tổng	16/20	sai test 1, 3, 8, 13
Duyệt tới $\sqrt{n}$ nhưng chỉ cộng $i$, quên ước $n / i$	16/20	sai test 1, 3, 8, 13
Duyệt i < n / 2 → sót ước $n / 2$	16/20	sai test 1, 3, 8, 13

Còn bẫy cộng căn hai lần ở số chính phương thì sao? Mình đã thử: với $n \le 10^7$, cộng thừa $\sqrt{n}$ không làm số chính phương nào thành "hoàn hảo" nên lời giải đó vẫn qua hết test – nhưng tổng ước bị tính sai, sang bài khác (tính tổng ước, đếm ước) là mất điểm ngay. Em nhớ luôn kiểm tra n / i != i.

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.003s	Full điểm
	Python	20/20	0.037s	Full điểm
Không bỏ n	C++	16/20	–	Mất 4 test
Quên ước n / i	C++	16/20	–	Mất 4 test
Sót ước n / 2	C++	16/20	–	Mất 4 test

Ghi chú của mình: mẹo "ước đi theo cặp, chỉ duyệt tới $\sqrt{n}$" sẽ còn dùng lại rất nhiều: đếm ước, kiểm tra số nguyên tố, tổng ước…

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 😇