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:

Test	x	n
1–20	1 … 20	1 … 20
21–70	14.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ện	Test	Cá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–20	20/20	20/20	20/20
Mức 2	$x, n \le 10^8$	21–70	20/50	50/50	50/50
Mức 3	$x, n \le 10^9$	71–100	0/30	0/30	30/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:

x = 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 vào (stdin) – sửa thoải mái2 3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

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 vào (stdin) – sửa thoải mái2 3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

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 vào (stdin) – sửa thoải mái2 13

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

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ách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. Đệ quy giảm n đi 1	C++	40/100	0.01s	tràn ngăn xếp (RE) 60 test
	Python	20/100	0.03s	tràn ngăn xếp (RE) 80 test
2. Vòng lặp nhân n lần	C++	70/100	> 1s	quá thời gian 30 test
	Python	48/100	> 1s	quá thời gian 52 test
3. Đệ quy chia đôi	C++	100/100	0.00s	Full điểm
	Python	100/100	0.02s	Full đ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 😇