Xin chào mn, tôi có thể tìm ước chung lớn nhất của 2 số nguyên rất lớn với ngôn ngữ c++ bằng cách nào, tôi nghĩ nó không giống với giải thuật tìm ước chung lớn nhất của 2 số nguyên nhỏ vì thời gian tìm kiếm là rất lâu. Xin mọi người giải đáp và xin cảm ơn.
Tìm GCD của 2 số nguyên rất lớn
Thực ra tốt nhất là lấy số lớn chia số bé lấy dư cho đến khi chia hết thì dừng, gọi là thuật toán Euclid.
Vì UCLN(a, b) = UCLN(a-b, b) = … = UCLN(b, a-q*b)
6 Likes
2 số RẤT LỚN thì giải thuật đệ quy vậy liệu có hiệu quả không nhỉ ?
Giả sử có 2 cố RẤT LỚN: a = 10^{1000}+1 và b=10^{1000} thì ta có:
UCLN(a, b) = UCLN(a-b, b) = UCLN(10^{1000}, 1) = UCLN(1, 0) = 1
Thì theo bạn vậy có hiệu quả không?
4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?