Untitled
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