Tuyển sinh 🎓 Mình nhận đào tạo lập trình giải thuật thi đấu: thi vào lớp 10 chuyên tin · thi học sinh giỏi tin học cấp tỉnh/thành · thi vào đội tuyển quốc gia · Olympic tin học sinh viên / ICPC · phỏng vấn thuật toán. Bấm vào đây để xem thông tin khóa học → Xem khóa học
Việt Nam Sơn
ZaloĐăng ký họcNhắn Zalo cho thầy

Lũy thừa nhanh

Lũy thừa nhanh
Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản Độ khó: Dễ Đệ quy Chia để trị

Đề bài

Nhiệm vụ của bài tập này là xây dựng chương trình con đệ quy tính lũy thừa $x^n$.

Dữ liệu vào: gồm hai số nguyên dương $x$ và $n$ $(1 \le x, n \le 10^9)$.

Kết quả: in một số nguyên duy nhất là $x^n$. Vì đáp án có thể rất lớn nên bạn hãy in kết quả sau khi chia lấy dư cho $10^9 + 7$.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Nguồn bài: VinhDinhCoder.

Ví dụ 1 – input
1 1
Ví dụ 1 – output
1
Ví dụ 2 – input
2 3
Ví dụ 2 – output
8

Lời mở đầu

Ví dụ 2: $2^3 = 8$. Bài này nghe thì dễ, nhưng với $n = 10^9$ thì nhân $n$ lần là quá chậm, còn đệ quy "giảm $n$ đi 1" thì sâu tới $10^9$ tầng – tràn ngăn xếp ngay. Lời giải đúng là lũy thừa nhanh: mỗi lần gọi đệ quy, số mũ giảm đi một nửa. Đây là một kỹ thuật cực kỳ quan trọng, sau này các bạn sẽ dùng lại ở rất nhiều bài số học (nghịch đảo modulo, tổ hợp, nhân ma trận...).

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ưởngchia đôi số mũCách 1giảm 1Cách 2vòng lặpCách 3lũy thừa nhanhTổng kếtkết quả

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

Bộ test có 100 test, mỗi test một cặp $(x, n)$. Đề không chia subtask, nhưng dữ liệu chia rõ 3 mức:

Testxn
1–201 … 201 … 20
21–7014.538 … $9{,}6 \cdot 10^{7}$20.336 … $9{,}4 \cdot 10^{7}$
71–100$1{,}1 \cdot 10^{8}$ … $9{,}8 \cdot 10^{8}$$2{,}6 \cdot 10^{8}$ … $9{,}8 \cdot 10^{8}$
  • Có $x$ gần $10^9$ (ví dụ $982\,959\,800$) – vẫn nhỏ hơn $10^9 + 7$, nhưng tích hai số như vậy cỡ $10^{18}$ nên phải dùng long long và lấy dư sau mỗi phép nhân.
  • Mình vẫn viết x %= MOD ở đầu cho chắc (nếu $x$ lớn hơn MOD thì phép nhân có thể tràn).

Kết quả chạy thật (giới hạn 1 giây):

MứcĐiều kiệnTestCách 1
(đệ quy giảm 1)		Cách 2
(vòng lặp)		Cách 3
(chia đôi)
Mức 1$x, n \le 20$1–2020/2020/2020/20
Mức 2$x, n \le 10^8$21–7020/5050/5050/50
Mức 3$x, n \le 10^9$71–1000/300/3030/30

Ý tưởngChia đôi số mũ

Thay vì $x^n = x^{n-1} \cdot x$ (giảm 1), ta dùng:

Công thức lũy thừa nhanh
$$x^n = \begin{cases} 1 & \text{nếu } n = 0 \\ \left(x^{n/2}\right)^2 & \text{nếu } n \text{ chẵn} \\ \left(x^{\lfloor n/2 \rfloor}\right)^2 \cdot x & \text{nếu } n \text{ lẻ} \end{cases}$$

Ví dụ $2^{13}$: cần $2^6$ (rồi bình phương, nhân thêm 2); $2^6$ cần $2^3$; $2^3$ cần $2^1$; $2^1$ cần $2^0 = 1$. Chỉ 5 lời gọi thay vì 13 phép nhân. Với $n = 10^9$ chỉ cần khoảng $\log_2 10^9 \approx 30$ lời gọi!

Điểm mấu chốt: tính $h = x^{\lfloor n/2 \rfloor}$ một lần, lưu vào biến rồi bình phương. Nếu viết luythua(x, n/2) * luythua(x, n/2) thì máy gọi 2 lần, cây đệ quy lại có $n$ nút – mất hết tác dụng.

Em nhập $x$, $n$ rồi bấm Tiếp: đầu tiên các lời gọi đi xuống (n giảm một nửa), chạm $n = 0$ thì các kết quả được tính ngược lên:

Ví dụ nhanh:

Cách 1Đệ quy giảm n đi 1

Cách đệ quy "tự nhiên" nhất: $x^n = x^{n-1} \cdot x$, điểm dừng $x^0 = 1$.

C++▶ Chạy tay từng dòng codeCách 1: x^n = x^(n−1)·x – mỗi lời gọi giảm n đi 1, ngăn xếp sâu n + 1 tầng.
Dữ liệu mẫu:
  1. Mỗi lời gọi chờ lời gọi con trả về rồi mới nhân thêm $x$, nên lúc sâu nhất ngăn xếp chứa $n + 1$ lời gọi cùng lúc.
  2. Ngăn xếp mặc định chỉ vài MB, mỗi lời gọi tốn vài chục byte → được khoảng vài trăm nghìn tầng. Với $n$ cỡ $10^7$ trở lên chương trình bị tràn ngăn xếp (Runtime Error).
Không gian$O(n)$ (ngăn xếp đệ quy)
Thời gian$O(n)$

Kết quả chạy thật: Bản C++ đúng 40/100 test, sai ở test 23, 27–31, 33, 36–38, 40–43, 45–46, 48–49, 53, 55–56, 60–62, 64–67, 69–100; test đúng chạy lâu nhất 0.01s. Bản Python đúng 20/100 test, sai ở test 21–100; test đúng chạy lâu nhất 0.03s. Các test "sai" ở đây đều là Runtime Error do tràn ngăn xếp: bản C++ chịu được tới $n$ cỡ $7 \cdot 10^5$ (qua mức 1 và 20 test mức 2), còn bản Python dừng ở giới hạn đệ quy 10 000 tầng nên chỉ qua mức 1.

Cách 2Vòng lặp nhân n lần

Bỏ đệ quy, nhân dồn $n$ lần bằng vòng for thì hết lo tràn ngăn xếp:

C++▶ Chạy tay từng dòng codeCách 2: vòng lặp nhân dồn n lần, lấy dư sau mỗi phép nhân.
Dữ liệu mẫu:
  1. Phải lấy dư ngay sau mỗi phép nhân: kq và x đều $< 10^9 + 7$ nên tích $< 1{,}1 \cdot 10^{18}$, vừa long long.
  2. Nhưng $n = 10^9$ phép nhân + chia lấy dư thì mất vài giây.
Không gian$O(1)$
Thời gian$O(n)$

Kết quả chạy thật: Bản C++ đúng 70/100 test, quá thời gian ở test 71–100; test đúng chạy lâu nhất 0.48s. Bản Python đúng 48/100 test, quá thời gian ở test 23, 27–30, 33, 36–38, 40–41, 46, 49, 53, 55, 61–62, 65–67, 69–100; test đúng chạy lâu nhất 0.91s. Cách này qua được mức 1 và mức 2 ($n \le 10^8$), quá thời gian ở mức 3.

Cách 3Đệ quy chia đôi – lũy thừa nhanh

C++▶ Chạy tay từng dòng codeCách 3: lũy thừa nhanh – mỗi lời gọi chia đôi số mũ, chỉ khoảng log₂n tầng.
Dữ liệu mẫu:
  1. long long h = luythua(x, n / 2); – gọi đệ quy đúng một lần, lưu kết quả vào h.
  2. h = h * h % MOD; – bình phương để được $x^{2 \lfloor n/2 \rfloor}$.
  3. Nếu $n$ lẻ thì $2 \lfloor n/2 \rfloor = n - 1$, nhân thêm một $x$ nữa.
  4. Độ sâu đệ quy chỉ khoảng $\log_2 n + 1 \le 31$ – không bao giờ tràn ngăn xếp.
  5. Python có sẵn hàm pow(x, n, MOD) làm đúng việc này, nhưng tự viết một lần để hiểu thì vẫn hơn.
Không gian$O(\log n)$ (ngăn xếp đệ quy)
Thời gian$O(\log n)$

Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.00s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 0.02s.

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

CáchNgôn ngữĐúngLâu nhấtGhi chú
1. Đệ quy giảm n đi 1C++40/1000.01stràn ngăn xếp (RE) 60 test
Python20/1000.03stràn ngăn xếp (RE) 80 test
2. Vòng lặp nhân n lầnC++70/100> 1squá thời gian 30 test
Python48/100> 1squá thời gian 52 test
3. Đệ quy chia đôiC++100/1000.00sFull điểm
Python100/1000.02sFull điểm
Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình, giới hạn 1 giây. Cách 1 bị Runtime Error vì tràn ngăn xếp (trên máy chấm có ngăn xếp lớn hơn thì qua được thêm vài test, nhưng $n = 10^9$ tầng thì không máy nào chịu nổi). Cách 2 chậm vì $O(n)$. Chỉ cách 3 – $O(\log n)$ – mới full điểm, chạy chưa tới 0,01 giây.
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 😇
Đọc thêm
Đăng nhận xét

Lũy thừa 1

Lũy thừa 1
Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản Độ khó: Dễ Đệ quy Chia để trị long long

Đề bài

Cho một số nguyên không âm $N$. Bạn hãy tính giá trị $2^N$.

Dữ liệu nhập: gồm một số nguyên không âm duy nhất là số $N$ $(0 \le N \le 50)$.

Dữ liệu xuất: một số nguyên dương chứa giá trị $2^N$.

Ví dụ – input
4
Ví dụ – output
16

Lời mở đầu

Tính lũy thừa là ví dụ kinh điển nhất khi học hàm đệ quy có giá trị trả về: mỗi lời gọi tính xong thì "trả" kết quả về cho lời gọi bên trên dùng tiếp. Bài có một cái bẫy nho nhỏ: $2^{50}$ vượt xa kiểu int. Mình sẽ giải bằng 2 cách: đệ quy từng bước $O(N)$ và đệ quy chia để trị $O(\log N)$ – nền móng của thuật toán lũy thừa nhanh sẽ học ở các bài sau.

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ộ test51 testÝ tưởngcây đệ quyCách 1bớt 1, O(N)Cách 2chia đôi, O(log N)

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

Số testGiá trị NĐáp ánSubtask
51Test thứ $i$ có $N = i - 1$, tức là đủ mọi giá trị $N = 0, 1, \dots, 50$từ $2^0 = 1$ đến $2^{50} = 1.125.899.906.842.624$Không chia subtask
  • Test 1 có $N = 0$: đáp án là $1$ – đây chính là điểm dừng của đệ quy, đừng quên!
  • Các test 32–51 ($N \ge 31$) có đáp án vượt $2^{31} - 1 \approx 2{,}1 \cdot 10^9$ – giới hạn của int. Đáp án lớn nhất $2^{50} \approx 1{,}1 \cdot 10^{15}$ vẫn nằm gọn trong long long (tới khoảng $9{,}2 \cdot 10^{18}$).
Bẫy tràn số
Mình đã thử nộp đúng code Cách 1 nhưng khai báo hàm kiểu int thay vì long long: kết quả chỉ 31/51 test – sai từ test 32–51. Với $N = 31$ chương trình in ra -2147483648, từ $N = 32$ trở đi in ra 0. Nên kiểu trả về của hàm phải là long long.

Ý tưởngHai cách chia nhỏ 2N

Hai công thức đệ quy
Cách 1 – bớt 1: $2^N = 2 \cdot 2^{N - 1}$, điểm dừng $2^0 = 1$. Cần $N$ lời gọi.
Cách 2 – chia đôi: đặt $h = 2^{\lfloor N/2 \rfloor}$ thì $2^N = h \cdot h$ nếu $N$ chẵn, $2^N = h \cdot h \cdot 2$ nếu $N$ lẻ. Mỗi lần gọi $N$ giảm một nửa nên chỉ cần khoảng $\log_2 N$ lời gọi.

Ví dụ $2^{13}$: $13 \to 6 \to 3 \to 1 \to 0$, chỉ 5 lời gọi; quay về: $2^0 = 1$, $2^1 = 1 \cdot 1 \cdot 2 = 2$, $2^3 = 2 \cdot 2 \cdot 2 = 8$, $2^6 = 8 \cdot 8 = 64$, $2^{13} = 64 \cdot 64 \cdot 2 = 8192$. Điều quan trọng là ở Cách 2 ta chỉ gọi luythua(n / 2) một lần, lưu vào h rồi nhân h * h. Nếu viết luythua(n / 2) * luythua(n / 2) thì cây đệ quy sẽ phân nhánh đôi và lại tốn $O(N)$ lời gọi.

Em chọn cách, nhập $N$ rồi bấm Tiếp: lời gọi đi xuống tới điểm dừng, rồi giá trị được trả ngược lên từng tầng (chữ xanh ↩):

Ví dụ nhanh:

Cách 1Đệ quy bớt 1: 2N = 2 · 2N−1

C++▶ Chạy tay từng dòng codeCách 1: luythua(n) = 2 × luythua(n − 1), dừng ở luythua(0) = 1.
Dữ liệu mẫu:
  1. if(n == 0) return 1; – điểm dừng, cũng xử lý luôn test $N = 0$.
  2. return 2 * luythua(n - 1); – máy phải chờ luythua(n - 1) tính xong mới nhân được với 2. Vì vậy các lời gọi xếp chồng trong ngăn xếp tới khi gặp điểm dừng, rồi mới lần lượt nhân ngược lên.
  3. Kiểu trả về long long (xem bẫy tràn số ở phần Bộ test). Hằng 2 kiểu int nhân với long long sẽ được tính theo long long, không lo tràn.
Không gian$O(N)$ (ngăn xếp)
Thời gian$O(N)$

Kết quả chạy thật: bản C++ đúng 51/51 test, test đúng chạy lâu nhất 0.003s; bản Python đúng 51/51 test, test đúng chạy lâu nhất 0.022s (Python có số nguyên lớn tuỳ ý nên không lo tràn số).

Cách 2Chia để trị: 2N = (2N/2)2

C++▶ Chạy tay từng dòng codeCách 2: chia để trị, h = luythua(n / 2) rồi trả về h × h (nhân thêm 2 nếu n lẻ).
Dữ liệu mẫu:
  1. long long h = luythua(n / 2); – gọi đệ quy đúng một lần cho nửa số mũ (chia nguyên).
  2. $N$ chẵn: $2^N = h^2$. $N$ lẻ: $N = 2 \cdot \lfloor N/2 \rfloor + 1$ nên phải nhân thêm 2.
  3. Với $N = 50$ chỉ có 7 lời gọi ($50 \to 25 \to 12 \to 6 \to 3 \to 1 \to 0$), so với 51 lời gọi của Cách 1. Ở bài này $N$ nhỏ nên 2 cách chạy nhanh như nhau, nhưng khi số mũ lên tới $10^{18}$ (kèm phép chia lấy dư) thì chỉ Cách 2 dùng được.
Không gian$O(\log N)$ (ngăn xếp)
Thời gian$O(\log N)$

Kết quả chạy thật: bản C++ đúng 51/51 test, test đúng chạy lâu nhất 0.003s; bản Python đúng 51/51 test, test đúng chạy lâu nhất 0.033s.

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

CáchNgôn ngữĐúngLâu nhấtGhi chú
Cách 1 nhưng dùng intC++31/510.003sSai ở test 32–51
1. Bớt 1C++51/510.003sFull điểm
Python51/510.022sFull điểm
2. Chia để trịC++51/510.003sFull điểm
Python51/510.033sFull điểm
Ghi chú của mình: cả 2 cách (C++ và Python) đều đạt full điểm, mỗi test dưới 0,05 giây. Riêng bản dùng int chỉ đúng 31/51 test vì tràn số. Hai điều cần nhớ: (1) luôn ước lượng kết quả lớn cỡ nào để chọn kiểu dữ liệu; (2) trong chia để trị, lưu kết quả lời gọi con vào biến rồi dùng lại, đừng gọi 2 lần.
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 😇
Đọc thêm
Đăng nhận xét
Đăng ký: Bài đăng (Atom)