atcoder
diff --git a/‎README.md
Copy file name to clipboardExpand all lines: README.md
+1Lines changed: 1 addition & 0 deletions b/‎README.md
Copy file name to clipboardExpand all lines: README.md
+1Lines changed: 1 addition & 0 deletions
diff --git a/‎extgcd.cpp
Copy file name to clipboard
+8Lines changed: 8 additions & 0 deletions b/‎extgcd.cpp
Copy file name to clipboard
+8Lines changed: 8 additions & 0 deletions
@@ -24,6 +24,7 @@ AtCoder解説放送ライブラリ集
 |名前|コード|説明|
 |:--|:--|:--|
 |GCD/LCM|[gcd.cpp](gcd.cpp)|最大公約数と最小公倍数|
+|extgcd|[extgcd.cpp](extgcd.cpp)|Ai+Bj=gcd(A,B)なるi,jを求める|
 |Combination|[comb.cpp](comb.cpp)|nCkをmod素数で求める|
 |Matrix|[mat.cpp](mat.cpp)|行列|
 |素数|[prime.cpp](prime.cpp)|素数列挙と素因数分解|
 
@@ -0,0 +1,8 @@
+// ai+bj=g
+// https://youtu.be/fDJpXN2R75A?t=6895
+ll extgcd(ll a, ll b, ll& i, ll& j) {
+  if (b == 0) { i = 1; j = 0; return a;}
+  ll p = a/b, g = extgcd(b,a-b*p,j,i);
+  j -= p*i;
+  return g;
+}