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

Được viết bởi: Codeforces


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^bab


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

Posted on March 16, 2021 07:11:26 PM


2
Donate free




Đăng nhập để tham gia thảo luận! Hoặc bạn có thể bình luận bằng facebook ở dưới.