Number Theory

Divisors

For example the divisors of a number like 12 (call it n) will be [1, 2, 3, 4, 6, 12].

If we look at them in pairs:

[1, 12]
[2, 6]
[3, 4]

We could just get the first three [1, 2, 3] — call them x — and [4, 6, 12] is y, so x * y = n. By getting x we could get y because we know n.

That saves time: while searching for divisors of n we only go up to √n. In our case (int)√12 = 3, and we get y by dividing n / x.

This runs in O(√n) instead of O(n).

vector<long long> divisors(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) {
                ret.push_back(n / i);
            }
        }
    }
    return ret;
}

For 12 we get [1, 12, 2, 6, 3, 4] — unsorted, but that’s fine.

The big deal comes with perfect squares like 16: without the i * i != n check we’d get [1, 16, 2, 8, 4, 4] with a duplicate 4.

This algorithm is efficient for finding divisors of one specific number.

But if we want divisors for every number from 1 to n, calling this for each number takes O(n√n). With n queries that’s O(n²√n) — TLE.

So we preprocess all divisors using a divisor sieve. It works on the fact: if i divides j, then i is a divisor of j. So for each i, we add it to all its multiples.

vector<vector<ll>> sieve(ll x) {
    vector<vector<ll>> ret(x + 1);
    for (int i = 1; i <= x; i++) {
        for (int j = i; j <= x; j += i) {
            ret[j].push_back(i);
        }
    }
    return ret;
}

Preprocessing: O(n log n). Each query: O(1) lookup.

Problems using this

• A. k-th divisor — get all divisors, sort, return k-th
• A. Divisors Queries — preprocess once, answer many queries
• R. Easy Number Challenge — uses divisor count sieve (see below)

Divisor Count

Same sieve idea, but instead of storing the list we just count:

vi divisors_cnt(ll x) {
    vi ret(x + 1, 0);
    for (int i = 1; i <= x; i++) {
        for (int j = i; j <= x; j += i) {
            ret[j]++;
        }
    }
    return ret;
}

ret[n] = number of divisors of n.

Problems using this

• R. Easy Number Challenge — sum of divisor counts over a 3D range

Prime Numbers

Divisors of 13 are [1, 13] — exactly two divisors → prime.

Divisors of 12 are [1, 2, 3, 4, 6, 12] — more than two → not prime.

Checking one number with the divisor function works fine.

But checking every number from 1 to n with that approach is O(n√n) — too slow.

Preprocess with the Sieve of Eratosthenes: assume every number is prime, then mark multiples of each prime as not prime.

vector<bool> sieve(ll n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (ll i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (ll j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

Preprocessing: O(n log log n). Each query: O(1).

Problems using this

• B - Is it Prime — single prime check
• Q. T-primes — extended below

T-primes

A T-prime is a number that has exactly 3 divisors.

When does a number have exactly 3 divisors? Only when it is the square of a prime:

• Divisors of p² are [1, p, p²] → exactly 3.

So to check if x is a T-prime:

1. Check if x is a perfect square.
2. Check if √x is prime (using precomputed sieve).

vector<bool> ret = sieve(1000005);

void solve() {
    ll x; cin >> x;
    if ((double)sqrt(x) - (ll)sqrt(x) == 0) {
        if (ret[sqrt(x)]) cout << "YES" << el;
        else cout << "NO" << el;
    } else {
        cout << "NO" << el;
    }
}

Problems using this

• Q. T-primes

Prime Factorization (SPF Sieve)

Prime factorization of 60 is 2 × 2 × 3 × 5.

One way: repeatedly divide by the smallest prime divisor.

The basic Eratosthenes sieve only tells us if a number is prime, not its smallest divisor. While building the sieve, store the smallest prime divisor (SPF) for each number.

vi sieve(ll n) {
    vi divided(n + 1, 0);
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (ll i = 2; i <= n; i++) {
        if (is_prime[i]) {
            divided[i] = i;
            for (ll p = i * i; p <= n; p += i) {
                is_prime[p] = false;
                if (divided[p] == 0) {
                    divided[p] = i;
                }
            }
        }
    }
    return divided;
}

Then factorize by dividing repeatedly:

vi prime_factorization(ll n, vi &divided) {
    vi ret;
    while (n != 1) {
        ll p = divided[n];
        ret.push_back(p);
        n /= p;
    }
    return ret;
}

For n = 60: 60 → 2, 30 → 2, 15 → 3, 5 → 5, 1 → [2, 2, 3, 5].

Preprocessing: O(n log log n). Each query: O(log n).

Problems using this

• G. Almost Prime — count numbers with exactly 2 distinct prime factors
• P. k-Factorization — output first k-1 prime factors, multiply rest

Almost Primes

A number is almost prime if it has exactly 2 distinct prime factors (multiplicity doesn’t matter).

Example: 6 = 2 × 3 → almost prime. 12 = 2 × 2 × 3 → still almost prime (distinct: {2, 3}).

After factorization, count distinct primes:

vi f = prime_factorization(i, d);
int cnt = 0;
for (int j = 0; j < f.size(); j++) {
    if (j == 0 || f[j] != f[j - 1]) cnt++;
}
if (cnt == 2) ans++;

Problems using this

• G. Almost Prime

Divisors of a Product

If n = p1^e1 × p2^e2 × ..., the number of divisors is (e1+1)(e2+1)....

For a product of many numbers, factor each one and combine exponents in a frequency map:

map<ll, ll> freq;
for (each number x in the array) {
    while (x > 1) {
        freq[spd[x]]++;
        x /= spd[x];
    }
}
ll ans = 1;
for (auto [pf, frq] : freq) {
    ans *= (frq + 1);
    ans %= MOD;
}

For large limits, use a linear sieve (faster SPF):

void sieve() {
    for (ll i = 2; i <= N; i++) {
        if (spd[i] == 0) {
            spd[i] = i;
            pr.push_back(i);
        }
        for (ll j = 0; j < pr.size() && pr[j] <= spd[i] && i * pr[j] <= N; j++) {
            spd[i * pr[j]] = pr[j];
        }
    }
}

Problems using this

• B. Divisors of Product

GCD Tricks

GCD of an array after adding x to every element

If we add x to every element: [a1+x, a2+x, ..., an+x].

Key identity: gcd(a, b) = gcd(a, b - a).

So gcd(a1+x, a2+x, ..., an+x) = gcd(a2-a1, a3-a1, ..., an-a1, a1+x).

Sort the array, compute GCD of all differences from a[0], then for each query x answer gcd(gc, x + a[0]).

sort(a.begin(), a.end());
ll gc = 0;
for (int i = 1; i < n; i++) {
    gc = gcd(gc, a[i] - a[0]);
}
// query x:
cout << gcd(gc, x + a[0]) << " ";

Problems using this

• C. Row GCD

GCD Arrays

Question: can we make every adjacent pair have GCD > 1 by deleting at most k elements?

Observation: if two numbers are both odd, their GCD is at least 1 but could still be 1 (e.g. 3 and 5). If at least one is even, GCD ≥ 2.

Count evens in [l, r]. The “bad” numbers are odds that can’t pair with an even. If remaining_odds <= k, answer is YES.

ll good = (r / 2) - ((l - 1) / 2);       // count of evens
ll remain = (r - l + 1) - good;           // count of odds
if (remain <= k) cout << "YES";

Edge case: l == r and l > 1 → YES (single element, no adjacent pair).

Problems using this

• X. GCD Arrays

Maximum GCD

For a set {1, 2, ..., n}, what’s the maximum GCD of any pair?

Best pair: (n/2, n) when n is even → GCD = n/2.

If n is odd, use (n-1, (n-1)/2) → GCD = (n-1)/2.

if (n % 2 != 0) n--;
cout << gcd(n, n / 2);

Problems using this

• Y. Maximum GCD

LCM (Least Common Multiple)

The LCM of two numbers is the smallest number that both divide.

Example: multiples of 4 are 4, 8, 12, 16... and multiples of 6 are 6, 12, 18.... The first common multiple is 12, so lcm(4, 6) = 12.

LCM and GCD

There is a direct link between GCD and LCM:

lcm(a, b) × gcd(a, b) = a × b

So:

lcm(a, b) = a / gcd(a, b) × b

We divide by GCD first to avoid overflow when a and b are large.

C++ has a built-in function in <numeric>:

#include <numeric>

ll lcm_ab = lcm(a, b);
// same as:
ll lcm_ab = a / gcd(a, b) * b;

LCM of Three Numbers

LCM is associative — compute two at a time:

ll lcm3(ll a, ll b, ll c) {
    return lcm(lcm(a, b), c);
}

Example: lcm(4, 6, 10)

lcm(4, 6) = 12
lcm(12, 10) = 60

LCM Challenge — Maximum LCM of Three Numbers

Problem: Given n, find the maximum value of lcm(i, j, k) where 1 ≤ i ≤ j ≤ k ≤ n.

The straightforward approach tries every triple:

for (ll i = 1; i <= n; i++)
    for (ll j = i; j <= n; j++)
        for (ll k = j; k <= n; k++)
            ans = max(ans, lcm3(i, j, k));

This is O(n³) — fine for small n, but TLE when n is up to 10⁶.

But we can prove the answer always comes from the last 5 numbers near n.

Why only check [n-4, n]?

1. lcm(i, j, k) ≥ max(i, j, k) = k — the LCM is at least the largest number in the triple.
2. So to maximize LCM, we want large numbers.
3. It can be shown that for any optimal triple, we can replace small values with numbers from {n-4, n-3, n-2, n-1, n} without getting a smaller LCM.
4. Any number ≤ n-5 is too far from n to beat a triple built from the top 5 values.

So instead of checking all O(n³) triples, we only check triples from the last 5 numbers — at most C(5+2, 3) = 35 triples (with i ≤ j ≤ k). That’s O(1).

ll ans = 0;
ll start = max(1LL, n - 4);
for (ll i = start; i <= n; i++) {
    for (ll j = i; j <= n; j++) {
        for (ll k = j; k <= n; k++) {
            ans = max(ans, lcm3(i, j, k));
        }
    }
}
cout << ans;

max(1, n-4) handles small n (when n < 5, we check from 1).

Examples

Notice how the best triple uses numbers right below n, not {1, 2, n}.

Problems using this

• E. LCM Challenge

LCM in Counting (Inclusion–Exclusion)

When counting multiples in [1, n]:

• Multiples of x: n / x
• Multiples of y: n / y
• Multiples of both x and y: n / lcm(x, y) (because a number divisible by both is divisible by their LCM)

ll cntX = n / x;
ll cntY = n / y;
ll cntBoth = n / lcm(x, y);

ll onlyX = cntX - cntBoth;
ll onlyY = cntY - cntBoth;

This is inclusion–exclusion: numbers divisible by both were counted twice, so subtract cntBoth once from each side.

Problems using this

• D. Plus Minus Permutation — sum of positions divisible by x minus sum divisible by y

Divisor Subtraction

Given n, repeatedly subtract its smallest divisor > 1. How many steps to reach 1?

• If n is even: smallest divisor is 2 → each step removes 2 → n/2 steps.
• If n is odd prime: can’t subtract anything > 1 properly → answer is 1.
• If n is odd composite: subtract smallest divisor d, then continue on the result.

if (n % 2 == 0) {
    cout << n / 2;
} else {
    ll d = n;
    for (ll i = 3; i * i <= n; i++) {
        if (n % i == 0) { d = i; break; }
    }
    if (d == n) cout << 1;           // prime
    else cout << 1 + (n - d) / 2;
}

Problems using this

• N. Divisor Subtraction

Different Divisors

Find the smallest number ≥ d+1 whose divisors are all different (i.e. a product of two distinct primes with gap ≥ d).

Find p = next_prime(d+1), then q = next_prime(p+d), answer = p * q.

Problems using this

• W. Different Divisors

Big Number Modulo

When n is a huge number stored as a string, we can’t convert it to long long. Compute n mod b digit by digit:

Process digits from right to left (or left to right with Horner’s method):

string s; cin >> s;
ll b; cin >> b;
reverse(s.begin(), s.end());
ll ans = 0, tenPowX = 1;
for (ll i = 0; i < s.size(); i++) {
    ll digit = s[i] - '0';
    ans = (ans + digit % b * tenPowX % b) % b;
    tenPowX = tenPowX * 10 % b;
}

Problems using this

• C. Remainder Quest

Some Important Identities

Sum of first n natural numbers

$$ 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2} $$

Sum of first n squares

$$ 1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6} $$

Sum of first n cubes

$$ 1^3 + 2^3 + 3^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 $$

Sum of first n fourth powers

$$ 1^4 + 2^4 + 3^4 + \dots + n^4 = \frac{n(n+1)(2n+1)(3n^2 + 3n - 1)}{30} $$

Fermat’s Little Theorem

Take a prime like 5, and any base not divisible by it — say 2. Look at 2^4:

2^4 = 16
16 mod 5 = 1

Try 3^4 and 4^4 too:

3^4 = 81   → 81 mod 5 = 1
4^4 = 256  → 256 mod 5 = 1

All three land on the same remainder, 1. That’s not a coincidence — it’s guaranteed by Fermat’s Little Theorem: for a prime p and any integer a not divisible by p,

a^(p-1) ≡ 1 (mod p)

(There’s an equivalent form, a^p ≡ a (mod p), that works even when a is a multiple of p. Divide both sides by a to get back the first form.)

Here ≡ (mod p) just means “same remainder when divided by p” — a ≡ b (mod p) iff p divides (a - b). It’s not saying the two sides are equal as numbers, just that they’re indistinguishable once you only care about remainders mod p. That’s what lets us swap a^(p-1) for 1 in the middle of a bigger calculation without changing the final answer mod p.

Why it matters: exponents repeat every p-1 steps

Because a^(p-1) ≡ 1 (mod p), the sequence a^0, a^1, a^2, ... mod p cycles with period p-1 — after every p-1 powers, you’re back where you started. That means if the exponent n is huge (too big to even store), we don’t need the real value of n at all — only how far it sits past the last full cycle.

Split n using ordinary division: n = (p-1)·q + r, so r = n mod (p-1). Then:

a^n = a^((p-1)q + r) = (a^(p-1))^q · a^r ≡ 1^q · a^r = a^r (mod p)

So a^n mod p only depends on r = n mod (p-1) — the q full cycles collapse to 1 and drop out entirely.

But n itself might be given as a giant string (thousands of digits, too big for any integer type). No problem — get n mod (p-1) the same way as in Big Number Modulo above, processing digits one at a time.

ll modP1 = p - 1;
ll r = 0;
for (char c : n_string) {
    r = (r * 10 + (c - '0')) % modP1;
}
// now compute a^r mod p directly — r is small

Once r is small, a^r mod p is trivial (loop it out, or binary exponentiation if r is still largish).

Example (p = 5)

All four confirm a^4 ≡ 1 (mod 5), which is exactly what lets a huge exponent n collapse down to just n mod 4.

(For a composite modulus instead of a prime, the same idea generalizes to Euler’s theorem, a^φ(m) ≡ 1 (mod m), using φ(m) in place of p-1.)

Problems using this

• 456B. Fedya and Maths — compute (1^n + 2^n + 3^n + 4^n) mod 5 for a huge n; reduces to checking n mod 4

Divisibility Rules

Take 405. Digit sum = 4+0+5 = 9, divisible by 3. Check directly: 405 / 3 = 135. ✓ Matches.

Rearrange the same digits: 540. Digit sum is still 9 — rearranging never changes the digit sum, so it never changes divisibility by 3. That’s the whole idea behind digit-sum rules: they only depend on which digits you have, not their order.

Not every rule works like that though — some depend on the last few digits instead. Full table:

Two families, and why the split matters

• Digit-sum rules (3, 9, and 11’s alternating-sum variant): order-independent — depend only on the digit multiset. Trivial to check even for huge numbers given as a string (sum the digits, or process with the running-remainder trick from Big Number Modulo).
• Suffix rules (2, 4, 5, 8, 10, 20, 25, …): depend only on the last j digits (j=1 for 2/5/10, j=2 for 4/20/25, j=3 for 8, …). These only matter for the value of the number as written — but if you’re allowed to rearrange digits freely, you instead get to choose what goes in those last j slots.

Combining rules for a composite divisor — coprime factors only

To check divisibility by some k, split k into pairwise coprime factors (gcd of any two pieces must be 1) and require all pieces to hold at once. This works because coprime divisibility conditions are independent.

Example: k = 60 = 2² × 3 × 5. Valid coprime factor pairs multiplying to 60:

(1, 60), (3, 20), (4, 15), (5, 12)

Something like (6, 10) is not valid — gcd(6,10) = 2 ≠ 1, so “divisible by 6 and by 10” doesn’t imply “divisible by 60” (counterexample: 30 passes both but isn’t divisible by 60).

Among the valid pairs, prefer whichever splits k into pieces that are each easy to check:

• (3, 20) → digit-sum check (3) + suffix-existence check (20: need a 0 for the last slot, and an even digit — possibly another 0 — for the slot before it). Both reduce to counting digit frequencies, no need to test actual permutations.
• (4, 15) or (5, 12) would work too, but checking divisibility by 4 needs the actual value of a 2-digit suffix (not just “any two even digits” — e.g. 24 works, 26 doesn’t), which is messier to reason about with rearrangement.

Problems using this

• M. Competitive Programmer (CF 1266A) — can the digits of y_i be rearranged into a multiple of 60? Split 60 = 3 × 20; check digit sum mod 3, and count zeros/evens for a valid X0 ending.