Fshl0

Extended GCD

Feb 5th, 2021
105
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int e_gcd (int a, int b, int &x, int &y) {
  2.     if (b == 0) {
  3.         x = 1;
  4.         y = 0;
  5.         return a;
  6.     }
  7.     int x1, y1;
  8.     int g = e_gcd (b, a % b, x1, y1);
  9.     x = y1, y = x1 - y1 * (a / b);
  10.     return g;
  11. }
RAW Paste Data