Ý tưởng

Đặt ~a=cx~, ~b=cy~ và ~\gcd(x,y)=1~. Khi đó ~xy=d/c~. Nếu ~d~ không chia hết cho ~c~ thì không tồn tại. Ngược lại, duyệt ~x~ từ ~\sqrt{d/c}~ giảm dần để tìm ước đầu tiên sao cho ~\gcd(x,(d/c)/x)=1~; cặp này cho tổng nhỏ nhất.

Độ phức tạp

~O(\sqrt{d/c})~.