Untitled

 avatar
unknown
plain_text
a year ago
846 B
9
Indexable
int ext(int n, int m, int &a1, int &b1){
    if (n == 0){
        a1 = 0;
        b1 = 1;
        return m;
    }
    int a2, b2;
    int ret = ext(m % n, n, a2, b2);
    a1 = b2 - a2 * (m / n);
    b1 = a2;
    return ret;
}


int solve(int y, int x, int s){
    int a, b, n;
    a = y, b = s, n = x;
    int a1, b1;
    int r = __gcd(a, n);
    if (b % r != 0){
        return void (cout << "No solution");
    }
    int val = ext(a / r, n / r, a1, b1);
    vector<int>sol(r);
    sol[0] = b / r * a1;
    for (int i = 1 ; i < r; ++i){
        sol[i] = sol[i - 1] + n / r;
    }
    for (int i = 0 ; i < r; ++i)
        sol[i] = (sol[i] + n) % n;

    /// returns values of X where (x * a) % n = b % n;
    for (int i = 0 ; i < r; ++i)
        cout << sol[i] << ' ';
    return *min(sol.begin(), sol.end());
}
Editor is loading...
Leave a Comment