# gcd, extgcd, crt --- 1. gcd * 說明： gcd最大公約數（greatest common divisor）的縮寫 * 求gcd(a, b)的方法 輾轉相除法！ $gcd(a, b) = gcd(b, a \mod b)$ $gcd(a, 0) = a$ ```cpp // 自訂函式寫法 int gcd(int a, int b) { if(b == 0) return a; return gcd(b, a % b); } ``` ```cpp // 迴圈寫法 while (b) { a %= b; swap(a, b); } ``` ```cpp // 內定 cout << __gcd(a, b) << endl; ``` 題目： [ZJ a024](https://zerojudge.tw/ShowProblem?problemid=a024) 2. extgcd * 說明 求 $ax+by=gcd(a, b)$的一組可行解 * 解析 [Extended Euclidean Algorithm](https://cp-algorithms.com/algebra/extended-euclid-algorithm.html) * 題目: [luogu P1082](https://www.luogu.org/problem/P1082)、[TIOJ 1098](https://tioj.ck.tp.edu.tw/problems/1098) 3. 中國剩餘定理(Chinese remainder theorem, 簡稱CRT) * 說明 extgcd 的應用 * 解析 [點進去第二篇](https://www.luogu.org/problemnew/solution/P4777?fbclid=IwAR22_13LyE1uKWAiZWcCbNlws65KYPB0Vkb8Xlb3xno-FG_L-86FYf9LXts) * 題目 [luogu P4777](https://www.luogu.org/problemnew/show/P4777) 4. 其他extgcd應用 模逆元！