Some Code Template Just for Fun.
#include "Number_Theory/Binary-Gcd.hpp"
#pragma once
#include "../Template/Template.hpp"
inline i64 binary_gcd(i64 a, i64 b) {
if (a == 0 || b == 0) return a + b;
char n = __builtin_ctzll(a);
char m = __builtin_ctzll(b);
a >>= n;
b >>= m;
n = std::min(n, m);
while (a != b) {
i64 d = a - b;
char s = __builtin_ctzll(d);
bool f = a > b;
b = f ? b : a;
a = (f ? d : -d) >> s;
}
return a << n;
}
#line 2 "Number_Theory/Binary-Gcd.hpp"
#line 2 "Template/Template.hpp"
#include <bits/stdc++.h>
using i64 = std::int64_t;
#line 4 "Number_Theory/Binary-Gcd.hpp"
inline i64 binary_gcd(i64 a, i64 b) {
if (a == 0 || b == 0) return a + b;
char n = __builtin_ctzll(a);
char m = __builtin_ctzll(b);
a >>= n;
b >>= m;
n = std::min(n, m);
while (a != b) {
i64 d = a - b;
char s = __builtin_ctzll(d);
bool f = a > b;
b = f ? b : a;
a = (f ? d : -d) >> s;
}
return a << n;
}