Merge pull request thuva4#395 from pranjalrai/master

thuva4 · web-flow · commit 4520f8faa52b · 2017-10-26T10:33:40.000+05:30
Added Extended Eulidean Algorithm in C++.
diff --git a/ExtendedEuclideanAlgorithm/C/extended_euclid.cpp b/ExtendedEuclideanAlgorithm/C/extended_euclid.cpp
@@ -0,0 +1,28 @@
+int d, x, y;
+
+void Extended_Euclid(int A, int B)   // a given equation of form Ax+By, extended euclid finds the gcd of A and B as well as the co-efficients of A and B
+{
+    if(B == 0)
+    {
+        d = A;
+        x = 1;
+        y = 0;
+    }
+    else
+    {
+        Extended_Euclid(B, A%B);
+        int temp = x;
+        x = y;
+        y = temp - (A/B)*y;
+    }
+}
+
+int main( )
+{
+    int m,n;
+    cin>>m>>n;
+extendedEuclid(m, n);
+cout << "The GCD of m and n is " << d << endl;
+cout << "Coefficient x and y are: "<< x <<  "and  " << y << endl;
+return 0;
+}
diff --git a/README.md b/README.md
@@ -65,6 +65,7 @@ Segmented Sieve |:+1:| :+1: |  |  | :+1: |  |  |  |
 Union Find |:+1:|:+1:|  | :+1: |  |  |  |  |  
 Xor swap |:+1:|:+1:|  |  |  |:+1:|:+1:|  |
 Connected-component labeling |  |  |  |  |:+1:|  |  |  |
+Extended Euclidean algorithm |  |  |  |  |:+1:|  |  |  |
 
 
 ### List of Algorithms :
