Hướng dẫn cho Phương trình Diophantine
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Bài toán chính là việc đếm số nghiệm nguyên dương của phương trình Diophantine tuyến tính hai ẩn. Như vậy ở bài toán trước là tính số nghiệm không âm, còn ở bài này là tính số nghiệm dương. Thuật toán cơ bản giống bài toán trước, có khác đôi chút ở việc xử lý tính \(t_1, t_2\).
Nếu \(UCLN(a, b)\) không là ước của \(c\) thì phương trình vô nghiệm và vì vậy câu trả lời là 0. Ngược lại, nếu \(UCLN(a, b)\) là ước của \(c\) thì ta dùng thuật toán Euclid mở rộng \(ext_gcd(a, b, d, x1, y1)\), khi đó nghiệm có dạng:
Bình luận