Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int int64_t
- int mod = 998244353;
- // a * x + b * y = d
- int gcd(int a, int b, int& x, int& y) {
- if (b == 0) {
- x = 1;
- y = 0;
- return a;
- }
- int x_ = 0, y_ = 0;
- int res = gcd(b, a % b, x_, y_);
- // b * x_ + (a % b) * y_ = d
- // b * x_ + (a - (a / b) * b) * y_ = d
- // a * y_ + b * (x_ - (a / b) * y_) = d
- x = y_;
- y = x_ - (a / b) * y_;
- return res;
- }
- int32_t main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- int a, b;
- cin >> a >> b;
- int x = 0, y = 0;
- gcd(a, b, x, y);
- cout << x << ' ' << y << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment