rembocoder

Untitled

Feb 16th, 2023
840
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.68 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int int64_t
  6.  
  7. int mod = 998244353;
  8.  
  9. // a * x + b * y = d
  10. int gcd(int a, int b, int& x, int& y) {
  11.     if (b == 0) {
  12.         x = 1;
  13.         y = 0;
  14.         return a;
  15.     }
  16.     int x_ = 0, y_ = 0;
  17.     int res = gcd(b, a % b, x_, y_);
  18.     // b * x_ + (a % b) * y_ = d
  19.     // b * x_ + (a - (a / b) * b) * y_ = d
  20.     // a * y_ + b * (x_ - (a / b) * y_) = d
  21.     x = y_;
  22.     y = x_ - (a / b) * y_;
  23.     return res;
  24. }
  25.  
  26. int32_t main() {
  27.     ios_base::sync_with_stdio(false);
  28.     cin.tie(0); cout.tie(0);
  29.     int a, b;
  30.     cin >> a >> b;
  31.     int x = 0, y = 0;
  32.     gcd(a, b, x, y);
  33.     cout << x << ' ' << y << endl;
  34. }
  35.  
Advertisement
Add Comment
Please, Sign In to add comment