Editorial for Phương trình Diophantine
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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:
Comments