i. GCD and Extended Euclid

$\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$ with $\gcd (a,0)=|a|$; it runs in $O(\log \min (a,b))$ steps (worst case: consecutive Fibonacci numbers). The extended Euclid algorithm also returns Bézout coefficients $ax+by=\gcd (a,b)$, which give modular inverses, linear Diophantine equations and CRT (Congruences and CRT).

ll extgcd(ll a, ll b, ll& x, ll& y) {                     // returns g = gcd(a, b) >= 0 and a x + b y = g
    x = 1, y = 0; ll x1 = 0, y1 = 1;                      // the quotients q below are exactly a/b's continued-fraction expansion
    while (b) { ll q = a / b; tie(a, b) = make_pair(b, a - q * b); tie(x, x1) = make_pair(x1, x - q * x1); tie(y, y1) = make_pair(y1, y - q * y1); }
    if (a < 0) a = -a, x = -x, y = -y;
    return a;
}
ll invMod(ll a, ll m) { ll x, y; ll g = extgcd(((a % m) + m) % m, m, x, y); return g != 1 ? -1 : ((x % m) + m) % m; }
ull binaryGcd(ull a, ull b) {                             // Stein: shifts and subtractions only
    if (!a || !b) return a | b;
    int s = __builtin_ctzll(a | b); a >>= __builtin_ctzll(a);
    while (b) { b >>= __builtin_ctzll(b); if (a > b) swap(a, b); b -= a; }
    return a << s;
}
ll lcmSafe(ll a, ll b) { return a / std::gcd(a, b) * b; }  // divide first; check against a bound with __int128 if needed

Property	Statement
basic divisibility	$a\mid b$ and $a\mid c\Rightarrow a\mid (b\pm c)$ and $a\mid bc$; $a\mid b$ and $b\mid c\Rightarrow a\mid c$ (transitive); $a\mid b$ and $b\mid a\Rightarrow |a|=|b|$
Bézout	$\{ax+by\}=g\mathbb{Z}$: the smallest positive combination is $g$; $ax+by=c$ is solvable iff $g\mid c$
every common divisor divides $g$	so $\gcd$ is the greatest in the divisibility order
coefficient size	the returned $
scaling, coprimality	$\gcd (ka,kb)=k\gcd (a,b)$; $\gcd (a/g,b/g)=1$
shifting	$\gcd (a,b)=\gcd (a+kb,b)=\gcd (a-b,b)$
Euclid’s lemma	$p$ prime, $p\mid ab\Rightarrow p\mid a$ or $p\mid b$; $\gcd (a,b)=1,a\mid bc\Rightarrow a\mid c$
products	$\gcd(a, b)\cdot\text{lcm}(a, b) =
arrays	$\gcd (a_0,\dots ,a_{n-1})=\gcd (a_0,a_1-a_0,\dots ,a_{n-1}-a_{n-2})$ (range add keeps the differences)
lattice points	the segment $(0,0)$–$(a,b)$ contains $\gcd (a,b)+1$ lattice points
special sequences	$\gcd (F_m,F_n)=F_{\gcd (m,n)}$; $\gcd (x^m-1,x^n-1)=x^{\gcd (m,n)}-1$
subarray gcds	the gcds of subarrays ending at $i$ take $O(\log V)$ distinct values

Proof: Euclid, its running time, Bézout and the coefficient bound

Correctness: $d\mid a,d\mid b⟺d\mid b,d\mid a-qb$, so the pairs $(a,b)$ and $(b,a\mathrm{mod}b)$ have the same common divisors. Time (Lamé): if the algorithm takes $k$ steps on $a>b$, then $a\ge F_{k+2}$ and $b\ge F_{k+1}$ by induction ($a\ge b+(a\mathrm{mod}b)$), so $k=O({\log }_{\phi }\min (a,b))$; consecutive Fibonacci numbers attain it. Extended: the loop maintains $ax+by=a_{\text{cur}}$ and $a{x}_1+b{y}_1=b_{\text{cur}}$ (true initially, and preserved because the new remainder is $a_{\text{cur}}-q{b}_{\text{cur}}$), so at the end $ax+by=g$. Bézout: the set $S=\{ax+by\}$ is closed under subtraction and integer multiples, so it is $d\mathbb{Z}$ for its least positive element $d$; $g$ divides every element, and $d$ is a combination equal to $g$ by the algorithm, so $S=g\mathbb{Z}$. Coefficient bound: the cofactor sequences satisfy $|x_i|\le b/g$ by the standard continuant argument: the final pair $(x_1,y_1)$ equals $\pm (b/g,-a/g)$, and the absolute values of the cofactors increase monotonically along the run.

Proof: the property table

Euclid’s lemma: if $\gcd (a,b)=1$ and $a\mid bc$, then $c=c(ax+by)=acx+(bc)y$ is divisible by $a$. gcd·lcm: by unique factorisation, exponents of $\gcd$ and $\text{lcm}$ are the minima and maxima of the exponents of $a,b$, and $\min +\max$ is the sum. Multiplicativity: with $a_1,a_2$ coprime, each prime of $b$ divides at most one of them, so the minima split. Arrays: any common divisor of the $a_i$ divides their differences, and conversely a common divisor of $a_0$ and all consecutive differences divides every $a_i$. Lattice points: points on the segment are $t(a,b)$ with $ta,tb\in \mathbb{Z}$, i.e. $t=k/g$ for $k=\mathrm{0..}g$. Fibonacci: $F_{m+n}=F_m{F}_{n+1}+F_{m-1}{F}_n$ gives $\gcd (F_{m+n},F_n)=\gcd (F_m{F}_{n+1},F_n)=\gcd (F_m,F_n)$ (consecutive Fibonacci numbers are coprime), which is Euclid’s step on indices. $x^n-1$: $x^m-1\equiv x^{m\mathrm{mod}n}-1(\mathrm{mod}{x}^n-1)$, again Euclid’s step on exponents. Subarray gcds: along a fixed right end, extending to the left the gcd only changes by dividing it, i.e. by a factor $\ge 2$, so there are at most ${\log }_{2}V+1$ distinct values. Binary gcd: $\gcd (2a,2b)=2\gcd (a,b)$, $\gcd (2a,b)=\gcd (a,b)$ for odd $b$, $\gcd (a,b)=\gcd (a,b-a)$; each round at least halves the larger odd value’s bit length, $O(\log )$ rounds.

Patterns

vector<pair<ll, ll>> subarrayGcdCounts(const vector<ll>& a) {   // {g, number of subarrays with gcd g}
    map<ll, ll> total; vector<pair<ll, ll>> cur;           // (gcd, count) of subarrays ending at i
    for (ll x : a) {
        vector<pair<ll, ll>> nxt{{x, 1}};
        for (auto [g, c] : cur) { ll h = std::gcd(g, x); if (nxt.back().first == h) nxt.back().second += c; else nxt.push_back({h, c}); }
        for (auto [g, c] : nxt) total[g] += c;
        cur = move(nxt);
    }
    return vector<pair<ll, ll>>(all(total));
}
vector<ll> divisorsOf(ll n) {                             // O(sqrt n), sorted
    vector<ll> small, big;
    for (ll d = 1; d * d <= n; d++) if (n % d == 0) { small.push_back(d); if (d != n / d) big.push_back(n / d); }
    small.insert(small.end(), big.rbegin(), big.rend()); return small;
}

$n\le$	$10^3$	$10^6$	$10^9$	$10^{12}$	$10^{15}$	$10^{18}$
max divisor count $d(n)$	32	240	1344	6720	26880	103680

$d(n)=O(n^{\epsilon })$ for any $\epsilon >0$ (sub-polynomial), though $O(n^{1/3})$ is a practical rule of thumb at contest-sized $n$; the divisor-pair sum ${\sum }_{i\le n}\lfloor n/i\rfloor =O(n\log n)$ drives most sieve-style precomputation (Floor Sums).

• GCD of a range: sparse table (idempotent) in $O(1)$ per query after $O(n\log n\log V)$, or a segment tree with point updates.
• Range add + range gcd: keep a segment tree of differences: $\gcd (a_l,\dots ,a_r)=\gcd (a_l,\gcd (d_{l+\mathrm{1..}r}))$.
• Counting pairs with $\gcd =g$: Möbius over multiples (Arithmetic Functions).
• Generalised Euclid / floor sums run the same recursion on $(a,b,c)$ (Floor Sums).