Thuật toánSố học 3 - Tính (a^b) % c - VNOI

Xét bài toán tính a^b%c, với % là dấu đồng dư thức và b có thể rất lớn (ví dụ b≤10^18).

Ở đây a^b là a mũ b

Thuật toán "ngây thơ"

a^b có thể viết là a.a.a.a… với b chữ a. Do đó ta có thể nhân b lần a để có được kết quả.



Trong mỗi lần lặp, biến ans chứa kết quả được nhân với a. Ngoài ra, ta cần đảm bảo a sẽ không vượt quá c trong các lần lặp, vì thế ta lấy phần dư khi chia ans cho c (ans = ans % c). Ta làm được vậy là nhờ tính chất (x.y)%n = ((x%n).(y%n))%n.
Vì vậy trong code trên ta tính (ans.a)%c bằng cách tính ((ans%c).(a%c))%c.

Độ phức tạp của thuật toán: O(b).

Thuật toán "chia để trị"

Dễ dàng nhận thấy thuật toán trên không hiệu quả, vì thế ta cần tìm thuật toán hiệu quả hơn. Ta có thể giải bài toán này với độ phức tạp O(log2(b)) bằng kĩ thuật lũy thừa bằng cách bình phương (exponentiation by squaring). Kĩ thuật này chỉ cần O(log2(b)) lần bình phương và O(log2(b)) phép nhân để ra kết quả. Rõ ràng cách giải này hiệu quả hơn nhiều lần so với thuật toán "ngây thơ".

Ta biết rằng a^b có thể được viết dưới dạng:

a^b = (a^(b/2))^2 nếu b chia hết cho 2.

a^b=a.(a^[b/2])^2 nếu b không chia hết cho 2.

a^b=1 nếu b=0.



Giả sử ta có a=2,b=5,c=5, khi đó kết quả là pow(2,5,5)
Do b lẻ, nên hàm pow(2,5,5) gọi hàm pow(2,2,5) để tính 2.pow(2,2,5)
Trong hàm pow(2,2,5), do b=2 chẵn nên pow(2,2,5)=pow(2,1,5)^2
Trong hàm pow(2,1,5), do b=1 lẻ nên pow(2,1,5)=2∗pow(2,0,5).

Trong hàm pow(2,0,5), do b=0 nên ta trả về 1.

Quay lại hàm pow(2,1,5): hàm này trả về giá trị 2.

Quay lại hàm pow(2,2,5): hàm này trả về giá trị 4.

Quay lại hàm pow(2,5,5): hàm này trả về giá trị (2.4^2)%5 = 32%5 = 2.

Vậy ta có 2^5%5=2.

Độ phức tạp của thuật toán: O(log2b)

Nguồn: VNOI.info