Положительные решения диофантового линейного уравнения

Question

Мне нужно решить диофантовое линейное уравнение, такое как ax + by = n (x, y неизвестно).

Пример проблемы: http://codeforces.com/contest/898/problem/B

В настоящее время я использую этот метод (код ниже), но я не могу использовать x < 0 или y <0.

Как я могу определить, существует ли положительное решение с x >= 0 и y> = 0, как его найти?

Код:

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

typedef long long ll;

pair<int,int> gcdExtended(int a, int b)
{
    if (a == 0)
        return make_pair(0, 1);
    int x, y;
    tie(x, y) = gcdExtended(b % a, a);
    return make_pair(y - b/a * x, x);
}

int main()
{
    int a, b, n;
    cin >> n >> a >> b;
    int d = __gcd(a, b);
    if (n % d == 0) {
        cout << "YES" << endl;
        int x, y;
        tie(x, y) = gcdExtended(a, b);
        cout << x*(n/d) << " " << y*(n/d) << endl;
    }
    else {
        cout << "NO" << endl;
    }
}