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 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) * 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









Auto comment: topic has been updated by Nourhan_Abo-Heba (previous revision, new revision, compare).
Auto comment: topic has been updated by Nourhan_Abo-Heba (previous revision, new revision, compare).