Tổng ước

Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản Độ khó: Dễ Đệ quy Ước số

Đề bài

Bạn được cho một số nguyên dương $N$. Bạn hãy tính tổng của tất cả các ước của số $N$.

Input: gồm một dòng duy nhất chứa một số nguyên dương $N$.

Output: gồm một dòng duy nhất, là tổng tất cả các ước số của số $N$.

Giới hạn: $1 \le N \le 10^{14}$.

• 40% số điểm đầu tiên có $N \le 10^6$.
• 40% số điểm tiếp theo có $N \le 10^{10}$.
• 20% số điểm còn lại không có giới hạn gì thêm.

Ví dụ – input

10

Ví dụ – output

18

Giải thích: $10$ có các ước là $\{1, 2, 5, 10\}$ và tổng các ước là $1 + 2 + 5 + 10 = 18$.

Lời mở đầu

Tính tổng ước là bài số học "kinh điển" mà bạn nào cũng gặp. Ở chương Đệ quy, mình dùng bài này để đi qua 3 mức: duyệt hết $N$ số (ăn 40%), ghép cặp ước tới $\sqrt{N}$ (full điểm), và cuối cùng là một hàm đệ quy "bóc" từng thừa số nguyên tố của $N$ – cách này vừa nhanh vừa cho các bạn thấy một công thức rất đẹp của số học.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

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ộ test100 testÝ tưởngCặp ước, σ(N)Cách 1O(N)Cách 2O(√N)Cách 3Đệ quy

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

Bộ test có 100 test, mỗi test là một số $N$. Thống kê theo nhóm:

Test	N	Đáp án
1 – 20	10 … 99	18 … 252
21 – 40	103 372 … 1 000 000	185 416 … 2 480 437
41 – 80	1 102 710 847 … 10 000 000 000	1 372 464 240 … 26 317 047 744
81 – 100	10 939 519 755 383 … 100 000 000 000 000	10 939 530 372 000 … 312 123 535 626 240

• Test 1 chính là ví dụ của đề ($N = 10$). Test 1 – 20 là các số có 2 chữ số, có cả số nguyên tố (đáp án $N + 1$).
• Mỗi nhóm đều có một test "chạm trần": test 40 là $10^6$, test 80 là $10^{10}$, test 100 là $10^{14}$.
• Đáp án lớn nhất cỡ $3{,}1 \cdot 10^{14}$ – vượt xa int, bắt buộc dùng long long.

Ba mức đúng như 3 subtask của đề:

Subtask	Điều kiện	Test	Cách ăn được
1 (40%)	$N \le 10^6$	1 – 40	Cách 1, 2, 3
2 (40%)	$N \le 10^{10}$	41 – 80	Cách 2, 3
3 (20%)	$N \le 10^{14}$	81 – 100	Cách 2, 3

Ý tưởngƯớc đi theo cặp, và tổng ước "tách" được theo thừa số nguyên tố

Quan sát 1 – ước đi theo cặp. Nếu $i$ là ước của $N$ thì $N / i$ cũng là ước. Trong mỗi cặp $(i,\ N/i)$ luôn có một số $\le \sqrt{N}$. Vậy chỉ cần cho $i$ chạy tới $\sqrt{N}$, mỗi lần gặp ước $i$ thì cộng luôn cả $i$ và $N/i$ (nếu $i = N/i$, tức $N$ là số chính phương, thì chỉ cộng một lần). Ví dụ $N = 36$: các cặp $(1, 36),$ $(2, 18),$ $(3, 12),$ $(4, 9),$ $(6, 6)$.

Quan sát 2 – tổng ước tách theo thừa số nguyên tố. Viết $N = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$. Mỗi ước của $N$ là chọn mỗi $p_i$ một số mũ từ $0$ tới $a_i$, nên khi nhân phân phối ra:

Công thức tổng ước

$\sigma(N)$ $= (1 + p_1 + \dots + p_1^{a_1}) \cdot (1 + p_2 + \dots + p_2^{a_2}) \cdots (1 + p_k + \dots + p_k^{a_k})$
Ví dụ $360 = 2^3 \cdot 3^2 \cdot 5$: $\sigma(360)$ $= (1+2+4+8)(1+3+9)(1+5)$ $= 15 \cdot 13 \cdot 6$ $= 1170$.

Công thức này rất hợp với đệ quy: hàm sigma(n, p) tìm ước nguyên tố nhỏ nhất $p$ của $n$, bóc hết $p^a$ ra khỏi $n$ để được tổng $1 + p + \dots + p^a$, rồi gọi lại chính nó với phần còn lại $n / p^a$. Điểm dừng: $n = 1$ (tổng ước là 1) hoặc $n$ không còn ước nào $\le \sqrt{n}$ – lúc đó $n$ là số nguyên tố, tổng ước là $n + 1$.

Em nhập $N$ rồi bấm Tiếp để xem các lời gọi đệ quy đi xuống (bóc từng thừa số) rồi trả kết quả ngược lên:

N =

Ví dụ nhanh:

Cách 1Duyệt mọi i từ 1 đến N – O(N)

Cách tự nhiên nhất: thử từng số $i = 1, 2, \dots, N$, số nào chia hết $N$ thì cộng vào tổng.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi i từ 1 đến n, O(n).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Tổng ước có thể lớn hơn $N$ (tới cỡ $3 \cdot 10^{14}$) nên s phải là long long; n và i cũng vậy vì $N$ tới $10^{14}$.
2. Vòng lặp chạy đúng $N$ lần. Với $N \le 10^6$ thì tức thì, nhưng $N = 10^{10}$ đã là 10 tỉ phép chia – không thể kịp 1 giây.

Không gian$O(1)$

Thời gian$O(N)$

Kết quả chạy thật: C++ đúng 40/100 test (test 1–40, chậm nhất 0.006 giây); test 41–100 bị quá thời gian. Python đúng 40/100 test (test 1–40, chậm nhất 0.137 giây); test 41–100 bị quá thời gian.

Cách 2Ghép cặp ước, i chạy tới căn N – O(√N)

Dùng quan sát 1: chỉ cho $i$ chạy khi $i \cdot i \le n$. Với $N = 10^{14}$ thì $\sqrt{N} = 10^7$ vòng lặp – C++ chạy chưa tới 0.05 giây.

C++▶ Chạy tay từng dòng codeCách 2: i chạy tới căn n, mỗi ước i kéo theo ước cặp đôi n / i.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Điều kiện i * i <= n thay cho i <= sqrt(n) để khỏi lo sai số số thực. i là long long nên i * i không tràn.
2. if(j != i): khi $N$ chính phương, ước $\sqrt{N}$ chỉ được cộng một lần (ví dụ 36 có cặp $(6, 6)$).

Không gian$O(1)$

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

Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất chỉ 0.040 giây. Python đúng 86/100 test (test 1–80, 83–84, 88–89, 91, 95, chậm nhất 0.876 giây); test 81–82, 85–87, 90, 92–94, 96–100 bị quá thời gian.

Cách 3Đệ quy bóc từng thừa số nguyên tố

Đây là cách cài đặt công thức ở phần ý tưởng. Hàm sigma(n, p) nhận thêm $p$ để biết "các số nguyên tố nhỏ hơn $p$ đã bóc hết rồi", lời gọi sau tìm tiếp từ $p + 1$ chứ không phải từ 2.

C++▶ Chạy tay từng dòng codeCách 3: đệ quy bóc từng thừa số nguyên tố, xem ngăn xếp lời gọi tăng lên rồi trả kết quả về.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Khung màu tím là lời gọi đang chạy, khung xám bên dưới là các lời gọi đang chờ kết quả, khung xanh là lời gọi vừa trả về.

1. Tìm ước nhỏ nhất: vòng while đầu tăng $p$ tới khi $p$ chia hết $n$ hoặc $p^2 > n$. Ước nhỏ nhất (khác 1) của một số luôn là số nguyên tố, nên $p$ tìm được chắc chắn là nguyên tố – không cần kiểm tra nguyên tố riêng.
2. Điểm dừng: nếu $p^2 > n$ thì $n$ không còn ước nào trong khoảng $[p, \sqrt{n}]$, mà các số nhỏ hơn $p$ đã bóc hết, nên $n = 1$ (trả về 1) hoặc $n$ là số nguyên tố (trả về $n + 1$).
3. Bóc $p^a$: vòng while(n % p == 0) chia $n$ cho $p$ tới hết, đồng thời t lần lượt là $p, p^2, \dots$ và s cộng dồn thành $1 + p + \dots + p^a$.
4. Lời gọi đệ quy s * sigma(n, p + 1): nhân phần vừa bóc với tổng ước của phần còn lại. Mỗi lời gọi bóc một số nguyên tố khác nhau, mà $10^{14}$ có tối đa 12 ước nguyên tố khác nhau, nên ngăn xếp lời gọi rất nông.

Không gian$O(k)$ – độ sâu đệ quy, $k \le 12$ là số ước nguyên tố khác nhau

Thời gian$O(\sqrt{N})$ trường hợp xấu nhất, thường nhanh hơn nhiều

Trường hợp xấu nhất vẫn là $N$ nguyên tố (phải thử $p$ tới $\sqrt{N}$), nhưng mỗi lần bóc được một thừa số thì $n$ nhỏ đi và $\sqrt{n}$ cũng nhỏ theo, nên trung bình chạy nhanh hơn cách 2 nhiều.

Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất chỉ 0.017 giây. Python đúng 100/100 test, test chậm nhất chỉ 0.369 giây.

Ghi chú của mình: cách 3 (C++) đúng 100/100 test, chậm nhất 0.017 giây; cách 2 cũng full điểm, chậm nhất 0.040 giây. Cách 1 chỉ qua được subtask 1 (40/100 test). Với Python thì vòng lặp tới $10^7$ lần của cách 2 bị quá thời gian ở subtask 3, còn cách 3 nhờ $n$ nhỏ đi sau mỗi lần bóc thừa số nên Python cũng full điểm (100/100 test, chậm nhất 0.37 giây) – một ví dụ rõ ràng cho thấy thuật toán tốt quan trọng hơn ngôn ngữ.

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 😇