EWTD

Untitled

Nov 28th, 2020 (edited)
480
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2.  
  3.  
  4. void extended_euclid(long a, long b, long *x, long *y, long *d){
  5.     long q, r, x1, x2, y1, y2;
  6.  
  7.     if (b == 0) {
  8.         *d = a, *x = 1, *y = 0;
  9.         return;
  10.     }
  11.  
  12.     x2 = 1, x1 = 0, y2 = 0, y1 = 1;
  13.  
  14.     while (b > 0) {
  15.         q = a / b;
  16.         r = a % b;
  17.         *x = x2 - q * x1;
  18.         *y = y2 - q * y1;
  19.         a = b;
  20.         b = r;
  21.         x2 = x1, x1 = *x;
  22.         y2 = y1, y1 = *y;
  23.     }
  24.     *d = a, *x = x2, *y = y2;
  25. }
  26.  
  27.  
  28.  
  29. int main(void){
  30.     long a = 4864, b = 3458, d, x, y;
  31.     extended_euclid(a, b, &x, &y, &d);
  32.     printf("x = %ld y = %ld d = %ld\n", x, y, d);
  33.     return 0;
  34. }
  35.  
RAW Paste Data