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

Revision en1, by Nourhan_Abo-Heba, 2025-12-06 13:52:51

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

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

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)