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 fastgcd. - 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 adding2and3into the box.
If
24 = 2^3 * 3^130 = 2^1 * 3^1 * 5^1thengcd(30,24)uses min exponents:2^min(3,1)*3^min(1,1)*5^min(0,1) = 2^1 * 3^1 = 6.lcmuses 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) = agcd(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
- 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
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) * bfor 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




