# GCD, LCM, Modular Arithmetic & Generating Divisors — a Codeforces-style Guide
Разница между en1 и en2, 295 символ(ов) изменены
↵
# 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)↵
↵
```cpp↵
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`↵
↵
```cpp↵
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↵
↵
```cpp↵
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)↵
↵
```cpp↵
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↵
↵
```cpp↵
#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↵
↵
↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Nourhan_Abo-Heba 2025-12-06 14:09:52 828
en2 Английский Nourhan_Abo-Heba 2025-12-06 14:00:36 295
en1 Английский Nourhan_Abo-Heba 2025-12-06 13:52:51 5399 Initial revision (published)