fork(1) download
copy 
  1. /*
  2.   Copyright 2012 Marek "p2004a" Rusinowski
  3.   Extended Euclidean algorithm
  4. */
  5. #include <cstdio>
  6.  
  7. int gcd(int a, int b, int &x, int &y) {
  8.   if (b == 0) {
  9.     x = 1, y = 0;
  10.     return a;
  11.   }
  12.   int d = gcd(b, a % b, y, x);
  13.   y -= x * (a / b);
  14.   return d;
  15. }
  16.  
  17. int main() {
  18.   int a, b, x, y;
  19.   scanf("%d %d", &a, &b);
  20.   int d = gcd(a, b, x, y);
  21.   printf("%d * %d + %d * %d = %d\n", x, a, y, b, d);
  22.   return 0;
  23. }
  24.  
Success #stdin #stdout 0.01s 2684KB
comments (?)
stdin
copy 
24 38
stdout
copy 
8 * 24 + -5 * 38 = 2
https://ideone.com/4aNgw
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!