最大公约数 gcd

最大公约数 gcd

欧几里得算法

速度不如内置函数！ 以 \(\mathcal O(\log(a+b))\) 的复杂度求解最大公约数。与内置函数 __gcd 功能基本相同（支持 \(a,b \leq 0\) ）。

inline int mygcd(int a, int b) { return b ? gcd(b, a % b) : a; }

位运算优化

略快于内置函数，用于卡常。

LL gcd(LL a, LL b) { // 卡常 gcd！！#define tz __builtin_ctzllif (!a || !b) return a | b;int t = tz(a | b);a >>= tz(a);while (b) {b >>= tz(b);if (a > b) swap(a, b);b -= a;}return a << t;#undef tz
}