GCD, LCM, Modular Arithmetic & Generating Divisors — a Codeforces-style Guide

Revision en3, by Nourhan_Abo-Heba, 2025-12-06 14:09:52

Tags: #math #number-theory #implementation #templates Difficulty: ★☆☆ — ★★☆ TL;DR: Treat every number as a multiset of prime powers (a “box of primes”).

  • gcd = take minimum exponent for each prime.
  • lcm = take maximum exponent for each prime.
  • Use Euclid (%) for fast gcd.
  • For modular division with prime modulus, use Fermat → inverse = pow(a, MOD-2).
  • Generate all divisors by recursion over prime powers.

1) Numbers = Boxes of Prime Factors

Example:

  • 12 = 2^2 * 3^1 → box: {2,2,3}
  • 6 = 2^1 * 3^1 → multiplying by 6 is like adding 2 and 3 into the box.

If

  • 24 = 2^3 * 3^1
  • 30 = 2^1 * 3^1 * 5^1 then gcd(30,24) uses min exponents: 2^min(3,1)*3^min(1,1)*5^min(0,1) = 2^1 * 3^1 = 6. lcm uses max exponents: 2^3 * 3^1 * 5^1 = 120.

2) GCD — Properties & Implementation

Properties:

  • gcd(a,b) = gcd(b,a%b) (Euclid)
  • gcd(a,0) = a
  • gcd(a,b) = gcd(a-b, b) (subtraction method — slow)

Example reduction: gcd(30,24) 30%24=6 → gcd(24,6) → 24%6=0 → gcd(6,0)=6

Fast C++ (Euclidean)

long long gcd(long long a, long long b){
    while(b){
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

Complexity: O(log(min(a,b))).


3) LCM — Use GCD to Avoid Overflow

Formula: lcm(a,b) = a / gcd(a,b) * b

long long lcm(long long a, long long b){
    if(a==0 || b==0) return 0;
    long long g = gcd(a,b);
    return (a / g) * b;
}

Complexity same as gcd.


4) Modular Arithmetic — Why and When

We use modular arithmetic to keep numbers small and prevent overflow, especially in competitive programming.

Reasons to Use It

  1. Prevent overflow:

cpp long long a = 1e18, b = 1e18; long long c = a * b; // Overflow! long long c_mod = (a % MOD) * (b % MOD) % MOD; // Safe 2. Problem explicitly asks:

> Output the answer modulo 10^9+7 3. Fast combinatorics & number theory: factorials, powers, nCr etc. grow extremely fast. 4. Division modulo prime: requires modular inverse. 5. Cyclic/wrapping behavior: clocks, circular arrays, hashing.

Rules

  • Only use modulo when required or to avoid overflow.
  • All operations should be modulo MOD.
  • Use modular inverse for division (not normal /).

Basic Operations

const ll MOD = 1e9+7;
ll add(ll a,ll b){ return (a%MOD + b%MOD) % MOD; }
ll sub(ll a,ll b){ return (a%MOD - b%MOD + MOD) % MOD; }
ll mul(ll a,ll b){ return (a%MOD * b%MOD) % MOD; }
ll powmod(ll a,ll e){ ... } // fast exponentiation
ll inv(ll a){ return powmod(a, MOD-2); } // division modulo prime
ll divide(ll a,ll b){ return mul(a, inv(b)); }

✅ Key idea: Modular arithmetic does not give the actual number, it gives the number modulo MOD, which is usually exactly what the problem expects.


5) Generating All Divisors

A) From prime factorization {(p_i, e_i)}

void gen_divisors_rec(int idx, ll cur,
                      const vector<pair<ll,int>>& fac,
                      vector<ll>& out){
    if(idx == fac.size()){ out.push_back(cur); return; }
    ll p = fac[idx].first;
    int e = fac[idx].second;
    ll val = 1;
    for(int k = 0; k <= e; ++k){
        gen_divisors_rec(idx+1, cur * val, fac, out);
        val *= p;
    }
}

B) From distinct primes (each exponent = 1)

void gen_from_primes(int idx, long long cur, 
                     const vector<long long>& primes,
                     vector<long long>& out){
    if(idx == primes.size()){ out.push_back(cur); return; }
    gen_from_primes(idx+1, cur, primes, out); // skip
    gen_from_primes(idx+1, cur * primes[idx], primes, out); // take
}

6) All-in-One Template

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007LL;

ll gcdll(ll a, ll b){
    while(b){ ll t = a % b; a = b; b = t; }
    return a;
}
ll lcmll(ll a, ll b){ return (a / gcdll(a,b)) * b; }

ll mod_mul(ll a, ll b){ return ((a%MOD)*(b%MOD))%MOD; }
ll mod_pow(ll a, ll e){
    ll res=1; a%=MOD;
    while(e){
        if(e&1) res = mod_mul(res,a);
        a = mod_mul(a,a);
        e >>= 1;
    }
    return res;
}
ll mod_inv(ll x){ return mod_pow(x, MOD-2); }
ll mod_div(ll a, ll b){ return mod_mul(a, mod_inv(b)); }

void gen_divisors_rec(int idx, ll cur, const vector<pair<ll,int>>& fac, vector<ll>& out){
    if(idx == fac.size()){ out.push_back(cur); return; }
    ll p = fac[idx].first;
    int e = fac[idx].second;
    ll val = 1;
    for(int k=0;k<=e;++k){
        gen_divisors_rec(idx+1, cur * val, fac, out);
        val *= p;
    }
}

int main(){
    ll a = 30, b = 24;
    cout << "gcd("<<a<<","<<b<<") = "<< gcdll(a,b) << "\n";
    cout << "lcm("<<a<<","<<b<<") = "<< lcmll(a,b) << "\n";

    vector<pair<ll,int>> fac = {{2,3},{3,1}}; // 24
    vector<ll> divs;
    gen_divisors_rec(0,1,fac,divs);
    sort(divs.begin(), divs.end());
    cout << "divisors of 24: ";
    for(ll d : divs) cout << d << ' ';
    cout << "\n";
}

7) Common Pitfalls

  • Overflow: use a / gcd(a,b) * b for lcm
  • Division modulo prime: always use modular inverse
  • Generating divisors: large exponents → many divisors → high memory/time

8) Practice Problems

  • Compute gcd & lcm for multiple queries
  • Count divisors from prime factorization
  • Generate divisors and check properties (sum, range)
  • Modular inverses & combinatorics

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Nourhan_Abo-Heba 2025-12-06 14:09:52 828
en2 English Nourhan_Abo-Heba 2025-12-06 14:00:36 295
en1 English Nourhan_Abo-Heba 2025-12-06 13:52:51 5399 Initial revision (published)