Math Toolkit

Quick Revisit

• USE WHEN: Problem needs floor/ceil division, GCD/LCM, primes, or sieve of Eratosthenes
• INVARIANT: ceil(a,b) = (a + b - 1) / b for positive a,b; gcd via Euclid; sieve starts at i*i
• TIME: O(1) GCD (practically), O(n log log n) sieve | SPACE: O(n) for sieve
• CLASSIC BUG: Integer overflow in (a + b - 1) / b or n*(n+1)/2—cast to long long before arithmetic
• PRACTICE: ../12-practice-ladders/01-ladder-1100-to-1400.md

Ten formulas cover most of the math you will ever need at the beginner level: floor/ceil division, arithmetic series, GCD/LCM, primality, and the Sieve of Eratosthenes. Every one has a C++ trap that costs a WA if you are not watching for it.

Difficulty: Beginner | Prerequisites: Complexity Analysis | CF tags: math, number theory, implementation | Typical range: CF 800–1400

Most CP math problems aren't about knowing these formulas—they're about recognizing that a problem reduces to one. The formula itself is two lines of code. The hard part is seeing "minimum operations to equalize all elements" and hearing "GCD of pairwise differences" in your head. These ten formulas are like a carpenter's tape measure: simple, indispensable, and dangerous if you misread them by one tick mark.

The Sieve of Eratosthenes dates to ~240 BC; Euclid's GCD algorithm (~300 BC) is one of the oldest known algorithms—predating most of recorded mathematics—and it is still the fastest practical GCD method. Keep this mnemonic handy: "Divide First, Cast Long, Start at i-squared"—the three rules that prevent the vast majority of math-toolkit WAs.

---

Contents

• Core Intuition
• Visual Walkthroughs
• C++ STL Reference
• Implementation
• Operations Reference
• Problem Patterns
• Contest Cheat Sheet
  • If I Had 5 Minutes
  • Before You Code Checklist
• Common Mistakes
  • Ceiling Division Pitfall for Negative a
  • LCM Overflow Detection
  • The Mistake That Teaches
• Useful Identities Cheat Sheet
• When NOT to Use This
• What Would You Do If...?
• Self-Test
• Debug This Exercises
• Practice Problems
• Recap
• Further Reading

---

Core Intuition

Why Seven Divided by Three Isn't Two

You need to split $n=7$ items into groups of $k=3$. How many groups? Obviously 3 (two full groups of 3, plus one leftover group of 1). You write:

int groups = n / k;  // 7 / 3 = 2   ... wrong!

C++ integer division truncates toward zero. It gives you the floor—how many full groups fit—but you need the ceiling: how many groups total, including the partial one.

The fix is (n + k - 1) / k, which gives (7 + 2) / 3 = 3. Correct—until someone passes a negative number and it breaks again.

That is the pattern for all ten formulas in this file: each one is two lines in a contest, each one has a trap that hands you a WA if you are not watching:

• Arithmetic sum overflows int before you divide by 2
• lcm(a, b) overflows because you multiplied before dividing by gcd
• Your primality test misses $n=1$ or loops past sqrt(n) due to floating-point rounding

The One Sentence

Ten math formulas cover most of the math in competitive programming—and every one has a C++ edge case that catches beginners.

Think of them as a mechanic's basic toolbox: wrench, screwdriver, pliers, hammer. You do not need power tools for most jobs. But if you grab the wrench backwards, you strip the bolt. These formulas are the wrench—simple, essential, and punishing if applied carelessly.

The Number Line: Floor vs Ceiling

                    floor(7/3)=2         ceil(7/3)=3
                         v                    v
    ----+----+----+----+----+----+----+----+----+---->
        0    1    2    3    4    5    6    7    8

    Groups of 3:
    |--- 3 ---|--- 3 ---|-- 1 --|
    group 1    group 2   group 3  <-- need 3 groups, not 2

For negative numbers, C++ truncates toward zero (not toward $-\mathrm{\infty }$):

    floor(-7/3) = -3       C++ gives: -7/3 = -2      ceil(-7/3) = -2
          v                               v                 v
    --+---+---+---+---+---+---+---+---+---+---+-->
     -4  -3  -2  -1   0   1   2   3   4   5

    C++ truncation != mathematical floor for negatives!

The Rules

+--------------------------------------------------------------------+
| CEILING DIVISION (positive a, b):  ceil(a/b) = (a + b - 1) / b    |
|                                                                    |
| GENERAL CEILING (any signs):                                       |
|   ceil(a/b) = a/b + (a % b != 0 && (a ^ b) >= 0)                 |
|                                                                    |
| OVERFLOW RULE: always divide BEFORE multiplying when possible.     |
|   lcm = a / gcd(a,b) * b       NOT  a * b / gcd(a,b)             |
|   sum = n/2 * (n+1)  if n even, else  n * ((n+1)/2)               |
+--------------------------------------------------------------------+

Ceiling division, step by step. Picture distributing items into fixed-size groups—the remainder forces one more group, which is exactly what ceiling captures and floor misses.

  Distributing 10 items into groups of 3:

  FLOOR (truncation):         CEILING (round up):
  10 / 3 = 3 full groups      ceil(10/3) = 4 groups

  |---3---|---3---|---3---|1|
  Item 1-3 Item 4-6 Item 7-9 Item 10
  Groups:  [====] [====] [====] [=]
           grp 1  grp 2  grp 3  grp 4

  If you only use floor, the last group is forgotten!

What the Code Won't Teach You

Correct formulas are necessary but not sufficient. Here is the judgment that turns them into solved problems.

Recognizing which formula applies. When the problem says "minimum operations to make all elements equal," you need to hear "GCD of pairwise differences." When it says "how many rectangles fit?" you need to hear "ceiling division." Pattern recognition is the bottleneck—not the math itself.

Edge cases cluster around 0, 1, and sign boundaries. Nearly every bug in this toolkit involves $n=0$, $n=1$, negative inputs, or overflow boundaries. When testing, always check these:

  +-- EDGE CASE RADAR ----------------------+
  |                                         |
  |  ceil_div(a,b)  -->  a=0? a<0? a=MAX?  |
  |  gcd(a,b)       -->  a=0? both 0?      |
  |  lcm(a,b)       -->  a=0? overflow?     |
  |  is_prime(n)    -->  n=0? n=1? n=2?     |
  |  sieve(n)       -->  n=0? n=1? size?    |
  |  sum(1..n)      -->  n=0? overflow?     |
  |                                         |
  +-- Test ALL of these EVERY time ---------+

Divide-first is a general principle, not just an LCM trick. Whenever a formula has both multiplication and division and an intermediate result divides evenly, do the division first. This applies to $n(n+1)/2$, LCM, binomial coefficients, and more.

Recognition flow—mapping problem statements to formulas:

  PROBLEM STATEMENT              RECOGNITION          FORMULA
  +---------------------+       +----------+       +---------------+
  | distribute n items  |-->--->| groups?  |-->--->| ceil-div      |
  | into groups of k    |       +----------+       +---------------+
  +---------------------+
  +---------------------+       +----------+       +---------------+
  | make all elements   |-->--->| diffs?   |-->--->| gcd of diffs  |
  | equal by adding d   |       +----------+       +---------------+
  +---------------------+
  +---------------------+       +----------+       +---------------+
  | two cycles align    |-->--->| periods? |-->--->| lcm           |
  | at what time?       |       +----------+       +---------------+
  +---------------------+

Edge case hotspots on the number line:

            overflow                                    overflow
            zone                                        zone
  <--###+---+-------+-------+-------+-------+-------+---+###-->
        |  -1       0       1       2              LLONG
        v           v       v                       MAX
      sign        zero   identity
      boundary    traps   traps

  Most bugs hide at: 0, 1, -1, and near max values

With those edge cases mapped, the next question is recognition: which formula does a given problem actually need?

When to Reach for This Toolkit

Trigger phrases in problem statements:

• "distribute $n$ items into groups of size $k$" → ceiling division
• "sum of first $n$ numbers" or "count pairs" → arithmetic series
• "GCD", "LCM", "coprime", "fraction" → GCD/LCM toolkit
• "is it prime" or "for all primes up to $n$" → trial division or sieve
• "$n\le {10}^6$" with "prime factorization" → sieve of Eratosthenes

Pattern Fingerprint: "count divisors" + n <= 10^6 → sieve; "groups/distribute" → ceil_div; "coprime/fraction" → gcd; "cycles align" → lcm

Counter-examples:

• "Find GCD of array" looks like you need Euclidean algorithm details, but std::gcd in a fold is enough. The real trick is usually what to do with the GCD, not how to compute it.
• "Count divisors of a single large $n$" looks like it needs a sieve, but trial division up to $\sqrt{n}$ suffices since you have only one number.

---

Visual Walkthroughs

These diagrams make the key algorithms concrete. Study them once; revisit when debugging.

GCD as Stepping Stones

gcd(48, 18)—the Euclidean algorithm repeatedly takes remainders:

Step 1:  48 = 2 * 18 + 12     -->  gcd(48, 18) = gcd(18, 12)

  0         18          36    48
  |----------+-----------|-----+
  |          |     12    |
                   ^--- remainder

Step 2:  18 = 1 * 12 + 6      -->  gcd(18, 12) = gcd(12, 6)

  0         12    18
  |----------+-----+
  |          | 6  |
               ^--- remainder

Step 3:  12 = 2 * 6 + 0       -->  gcd(12, 6) = gcd(6, 0) = 6

  0      6     12
  |------+------+
  |  6   |  6   |  remainder = 0, done!

  Answer: gcd(48, 18) = 6

At most $O(\log (min(a,b)))$ steps—the remainder shrinks by at least half every two steps.

Here is the same algorithm shown as repeated remainders, tiling the larger number with the smaller until nothing is left over:

  Finding gcd(100, 35) step-by-step

  100 = 2*35 + 30          gcd(100, 35) = gcd(35, 30)
  +----+----+30|
  |  100    | 35|
  +----+----+---+

  35 = 1*30 + 5            gcd(35, 30) = gcd(30, 5)
  +---+5|
  | 35| 30|
  +---+--+

  30 = 6*5 + 0             gcd(30, 5) = gcd(5, 0) = 5
  +--+--+--+--+--+--+
  |5 |5 |5 |5 |5 |5 |  (all 30 is covered by 5)
  +--+--+--+--+--+--+

  Answer: gcd(100, 35) = 5

Sieve of Eratosthenes: Crossing Off Multiples

Mark composites for primes up to $n=30$:

Start:  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
        21 22 23 24 25 26 27 28 29 30

Cross off multiples of 2 (start from 2*2=4):
        2  3  .  5  .  7  .  9  .  11  .  13  .  15  .  17  .  19  .
        21  .  23  .  25  .  27  .  29  .

Cross off multiples of 3 (start from 3*3=9):
        2  3  .  5  .  7  .  .  .  11  .  13  .  .   .  17  .  19  .
        .   .  23  .  25  .  .   .  29  .

Cross off multiples of 5 (start from 5*5=25):
        2  3  .  5  .  7  .  .  .  11  .  13  .  .   .  17  .  19  .
        .   .  23  .  .   .  .   .  29  .

  Stop: next prime is 7, and 7*7 = 49 > 30.

  Primes: 2 3 5 7 11 13 17 19 23 29

Key optimization: for prime $p$, start crossing from $p^2$ (smaller multiples were already crossed off by smaller primes).

Sieve Logic: Why We Start from p^2

  Finding primes up to 15:

  Initial:  2  3  4  5  6  7  8  9  10 11 12 13 14 15

  Prime 2: multiples are 4, 6, 8, 10, 12, 14
  Remove:  2  3  X  5  X  7  X  9  X  11  X  13  X  15

  Prime 3: multiples are 9, 12, 15
           (6, 12 already crossed by 2)
  Remove:  2  3  X  5  X  7  X  X  X  11  X  13  X  X

  Prime 5: next multiple is 25 > 15, so stop!

  Remaining (primes): 2 3 5 7 11 13

  Why start from p^2?  Because 2*3=6, 2*5=10 were already handled.
                       First "new" multiple is p*p = p^2.

Arithmetic Sum: Why $n(n+1)/2$ Works

Sum $1+2+3+4+5$:

  Pair them from outside in:

    1   2   3   4   5
    +   +   +   +   +
    5   4   3   2   1
    -----------------
    6   6   6   6   6   =  5 * 6 = 30

  But we counted everything twice, so divide by 2:

    Sum = 5 * 6 / 2 = 15

  General: Sum(1..n) = n * (n+1) / 2

---

C++ STL Reference

Before writing anything from scratch, check what C++ already provides.

Function / Header	What it does	Gotchas
a / b (integers)	Truncation toward zero	Not floor for negatives: -7/3 = -2
a % b (integers)	Remainder with sign of a	-7 % 3 = -1 (not 2)
std::gcd(a, b) <numeric>	Greatest common divisor	C++17. gcd(0, 0) = 0. Works with negatives.
std::lcm(a, b) <numeric>	Least common multiple	C++17. Can overflow! Use a / gcd(a,b) * b.
__int128	128-bit integer	GCC extension. No cin/cout support.
__builtin_ctzll(x)	Count trailing zeros (64-bit)	Undefined for $x=0$.
sqrt(x), sqrtl(x)	Square root (double / long double)	Floating point! Check s*s <= n && (s+1)*(s+1) > n.
log2(x)	${\log }_{2}x$ (double)	Use __lg(x) or bit_width for exact integer log2.
bit_width(x) <bit> C++20	$\lfloor {\log }_{2}x\rfloor +1$	Returns 0 for $x=0$. Unsigned only.

---

Implementation

Minimal: Floor and Ceiling Division

#include <bits/stdc++.h>
using namespace std;

// Ceiling division for positive a, b
long long ceil_div(long long a, long long b) {
    return (a + b - 1) / b;
}

// General ceiling division (any signs)
long long ceil_div_general(long long a, long long b) {
    return a / b + (a % b != 0 && ((a ^ b) >= 0));
}

// General floor division (mathematical floor, not C++ truncation)
long long floor_div(long long a, long long b) {
    return a / b - (a % b != 0 && ((a ^ b) < 0));
}

int main() {
    cout << ceil_div(7, 3) << "\n";           // 3
    cout << ceil_div(6, 3) << "\n";           // 2
    cout << ceil_div(1, 1000000) << "\n";     // 1
    cout << ceil_div_general(-7, 3) << "\n";  // -2
    cout << floor_div(-7, 3) << "\n";         // -3
}

Minimal: Arithmetic Series (Overflow-Safe)

#include <bits/stdc++.h>
using namespace std;

// Sum of a..b inclusive (overflow-safe for int range)
long long sum_range(long long a, long long b) {
    if (a > b) return 0;
    long long cnt = b - a + 1;
    // one of (a+b) or cnt is even, divide the even one first
    if (cnt % 2 == 0)
        return (cnt / 2) * (a + b);
    else
        return cnt * ((a + b) / 2);
}

int main() {
    cout << sum_range(1, 100) << "\n";             // 5050
    cout << sum_range(1, 1000000000LL) << "\n";    // 500000000500000000
    cout << sum_range(5, 5) << "\n";               // 5
    cout << sum_range(10, 1) << "\n";              // 0 (empty range)
}

Minimal: GCD, LCM, and Related

#include <bits/stdc++.h>
using namespace std;

int main() {
    // std::gcd and std::lcm (C++17, in <numeric>)
    cout << gcd(48, 18) << "\n";          // 6
    cout << gcd(0, 5) << "\n";            // 5
    cout << gcd(0, 0) << "\n";            // 0

    // Safe LCM: divide before multiply to avoid overflow
    auto safe_lcm = [](long long a, long long b) -> long long {
        if (a == 0 || b == 0) return 0;
        return a / gcd(a, b) * b;
    };
    cout << safe_lcm(12, 18) << "\n";     // 36

    // GCD of entire array
    vector<int> v = {12, 18, 24, 36};
    int g = v[0];
    // Invariant: g == gcd of all elements processed so far
    for (int x : v) g = gcd(g, x);
    cout << g << "\n";                    // 6
}

  LCM OVERFLOW vs SAFE PATH

  a = 10^18    b = 10^18 - 1    gcd = 1

  UNSAFE:  a * b = 10^36  --> OVERFLOW! <--- silent bug
           |
           v
           / gcd = 10^36  --> garbage

  SAFE:    a / gcd = 10^18
           |
           v
           * b = ~10^36   --> still overflows!

  Wait -- even safe LCM can overflow if result > 9.2*10^18!
  +---------------------------------------------+
  | RULE: if a/gcd(a,b) > LLONG_MAX/b, the LCM  |
  |       itself doesn't fit in long long.       |
  +---------------------------------------------+

Minimal: Primality Test (Trial Division with 6k+/-1)

#include <bits/stdc++.h>
using namespace std;

bool is_prime(long long n) {
    if (n < 2) return false;
    if (n < 4) return true;             // 2 and 3
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (long long i = 5; i * i <= n; i += 6) {
        // Invariant: all composites with smallest factor < i are already rejected
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

int main() {
    cout << is_prime(1) << "\n";          // 0
    cout << is_prime(2) << "\n";          // 1
    cout << is_prime(997) << "\n";        // 1
    cout << is_prime(1000000007) << "\n"; // 1  (classic CP prime)
}

The 6k±1 optimization explained—why the loop only checks i and i+2:

  6k-1 / 6k+1 PRIMALITY CHECK PATTERN

  Every integer mod 6 falls into one of six residue classes:

  class    0     1     2     3     4     5
           |     |     |     |     |     |
           v     v     v     v     v     v
         div6   ---  div2  div3  div2   ---
                 ^                       ^
                 |                       |
           only these two classes can hold primes > 3

  The loop checks i and i+2 at stride 6:

  i---->  5  7  |  11 13  |  17 19  |  23 25  |  29 31
          #  #  |   #  #  |   #  #  |   #  #  |   #  #
          +--6--+---+--6--+---+--6--+---+--6--+

  Checks 2 out of every 6 numbers -- 3x fewer than all odds

Minimal: Sieve of Eratosthenes

#include <bits/stdc++.h>
using namespace std;

vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; (long long)i * i <= n; i++)
        if (is_prime[i])
            // Invariant: all composites with smallest factor < i are already marked false
            for (int j = i * i; j <= n; j += i)
                // Invariant: j is a multiple of i not yet marked by this prime
                is_prime[j] = false;
    return is_prime;
}

int main() {
    auto ip = sieve(100);
    for (int i = 2; i <= 100; i++)
        if (ip[i]) cout << i << " ";
    // 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
}

Minimal: Smallest Prime Factor Sieve (for Fast Factorization)

#include <bits/stdc++.h>
using namespace std;

vector<int> spf_sieve(int n) {
    vector<int> spf(n + 1);
    iota(spf.begin(), spf.end(), 0);  // spf[i] = i initially
    for (int i = 2; (long long)i * i <= n; i++)
        if (spf[i] == i)              // i is prime
            // Invariant: spf[j] == j means j hasn't been assigned a smaller factor yet
            for (int j = i * i; j <= n; j += i)
                if (spf[j] == j)
                    spf[j] = i;       // i is the smallest prime factor of j
    return spf;
}

// Factorize any number <= n in O(log n) using SPF table
vector<pair<int,int>> factorize(int x, const vector<int>& spf) {
    vector<pair<int,int>> factors;
    while (x > 1) {
        int p = spf[x], cnt = 0;
        // Invariant: all prime factors smaller than p have been extracted
        while (x % p == 0) { x /= p; cnt++; }
        factors.push_back({p, cnt});
    }
    return factors;
}

int main() {
    auto spf = spf_sieve(1000000);
    // Factorize 360 = 2^3 * 3^2 * 5
    for (auto [p, e] : factorize(360, spf))
        cout << p << "^" << e << " ";  // 2^3 3^2 5^1
}

How the SPF sieve assigns smallest prime factors:

  SMALLEST PRIME FACTOR SIEVE -- first 16 numbers

  Start: spf[i] = i for all i
  idx:  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
  spf:  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16

  p=2 is prime -- mark from 2*2=4:
  idx:  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
  spf:  2  3 *2  5 *2  7 *2  9 *2 11 *2 13 *2 15 *2
                 ^     ^     ^     ^     ^     ^     ^
                 +--+--+--+--+--+--+--+--+--+--+-->  set to 2

  p=3 is prime -- mark from 3*3=9:
  idx:  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
  spf:  2  3  2  5  2  7  2 *3  2 11  2 13  2 *3  2
                                ^                ^
                                +--- set to 3 ---+

  Done: 4*4=16, outer loop stops.
  Primes have spf[i]=i  -->  2, 3, 5, 7, 11, 13

  Factorize 12 using SPF table:
  12 -> spf[12]=2 -> 12/2=6 -> spf[6]=2 -> 6/2=3 -> spf[3]=3 -> done
  Result: 12 = 2 * 2 * 3

Explained: Powers of 2 and Quick Estimates

#include <bits/stdc++.h>
using namespace std;

int main() {
    // The CP estimation rule: 2^10 ~ 10^3
    // So 2^20 ~ 10^6, 2^30 ~ 10^9, 2^40 ~ 10^12

    // How many binary search iterations for range [1, 10^6]?
    // log2(10^6) ~ 20. So binary search needs ~20 iterations.
    cout << "log2(1e6) = " << log2(1e6) << "\n";   // ~19.93

    // Quick complexity validation:
    // n = 10^5, O(n log n) ~ 10^5 * 17 ~ 1.7 * 10^6. Fast enough.
    // n = 10^6, O(n log n) ~ 10^6 * 20 = 2 * 10^7. Still fine.
    // n = 10^5, O(n * sqrt(n)) ~ 10^5 * 316 ~ 3 * 10^7. OK.

    // Geometric series: 2^0 + 2^1 + ... + 2^(n-1) = 2^n - 1
    // This is why bitmask DP with n=20 does 2^20 - 1 ~ 10^6 work.
    cout << "2^20 - 1 = " << ((1 << 20) - 1) << "\n";  // 1048575

    // GOTCHA: 1 << 31 overflows int. Use 1LL << k for k >= 31.
    long long big = 1LL << 40;
    cout << "2^40 = " << big << "\n";  // 1099511627776 ~ 10^12
}

---

Operations Reference

Every function in this toolkit, with its time and space complexity and the trap most likely to bite you:

Operation	Time	Space	Notes
ceil_div(a, b)	$O(1)$	$O(1)$	Positive inputs only
sum_range(a, b)	$O(1)$	$O(1)$	Use long long for $n>46340$
gcd(a, b)	$O(\log min(a,b))$	$O(1)$	At most ~43 steps for 64-bit
lcm(a, b)	$O(\log min(a,b))$	$O(1)$	Divide first to avoid overflow
is_prime(n)	$O(\sqrt{n})$	$O(1)$	Fine for single queries up to ${10}^{18}$
sieve(n)	$O(n\log \log n)$	$O(n)$	Practical for $n\le {10}^7$
spf_sieve(n)	$O(n\log \log n)$	$O(n)$ ints	Enables $O(\log n)$ factorization
Factorize via SPF	$O(\log n)$ per query	$O(1)$	After $O(n)$ sieve precomputation
Count divisors of $n$	$O(\sqrt{n})$	$O(1)$	Trial division
Count primes $\le n$	$O(n\log \log n)$	$O(n)$	Via sieve

---

Problem Patterns

Knowing the formulas is half the battle—here is how to spot which one a problem needs.

  MATH TOOLKIT PATTERN MATCHER

  "groups" / "distribute" / "batches"
       |
       v
  +-- CEILING DIVISION --+
  |  (n + k - 1) / k     |
  +-----------------------+

  "pairs" / "handshakes" / "choose 2"
       |
       v
  +-- ARITHMETIC SERIES --+
  |  n * (n - 1) / 2      |
  +------------------------+

  "coprime" / "fraction" / "GCD"
       |
       v
  +-- GCD / LCM ----------+
  |  std::gcd + fold       |
  +------------------------+

  "prime" / "factor" / "sieve"
       |
       +---> one number?   --> trial division O(sqrt n)
       +---> many numbers? --> sieve O(n log log n)

Ceiling Division for Distribution

"Distribute $n$ items among $k$ groups" or "how many pages of size $k$?"—use (n + k - 1) / k. Appears in problems about scheduling, pagination, round counts, and minimum operations.

int pages = (n + page_size - 1) / page_size;
int rounds = (total_work + workers - 1) / workers;

CF 1328A - Divisibility Problem, CF 1850C - Word on the Paper

Counting Pairs with Arithmetic Sum

"How many pairs $(i,j)$ with $i<j$ exist in $n$ elements?" The answer is $(\genfrac{}{}{0ex}{}{n}{2})=n(n-1)/2$. More generally, the contribution technique uses arithmetic sums: element at position $i$ pairs with $i$ elements before it.

long long pairs = (long long)n * (n - 1) / 2;

CF 1399A - Remove Smallest, CSES Apartments

GCD to Simplify or Check Divisibility

When a problem asks "can we make all elements equal by adding or subtracting $d$?" or involves fractions, compute the GCD of the differences. If the $gcd$ of all pairwise differences is $g$, any valid step size must divide $g$.

int g = 0;
// Invariant: g == gcd of all abs(x - a[0]) processed so far; starts at 0 (identity)
for (int x : a) g = gcd(g, abs(x - a[0]));

CF 1154A - Restoring Three Numbers, CF 1547C - Pair Programming

LCM for Cycle Synchronization

"When do two cycles of length $a$ and $b$ align?" Answer: $\text{lcm}(a,b)$. For multiple cycles, fold LCM across the array and watch for overflow.

long long L = 1;
for (int x : cycles) {
    // Invariant: L == lcm of all cycle lengths processed so far
    L = L / gcd(L, (long long)x) * x;  // divide first!
    if (L > 1e18) { /* overflow / answer too large */ break; }
}

CF 1295A - Display The Number

Sieve Then Query

Precompute primes (or smallest prime factors) up to ${10}^6$ or ${10}^7$, then answer many queries in $O(1)$ or $O(\log n)$ each. Classic sieve-then-lookup.

auto ip = sieve(1000000);
// answer q queries
while (q--) {
    int x; cin >> x;
    cout << (ip[x] ? "YES" : "NO") << "\n";
}

CSES Counting Divisors, CF 1771C - Hossam and Trainees

Complexity Validation via Powers of 2

Before coding, estimate: is $O(n\log n)$ fast enough? Use $2^{10}\approx {10}^3$ to quickly compute ${\log }_2(n)$:

• $n={10}^5$: ${\log }_2\approx 17$, so $n\log n\approx 1.7\times {10}^6$ OK
• $n={10}^6$: ${\log }_2=20$, so $n\log n=2\times {10}^7$ OK
• Bitmask with $n=20$: $2^{20}\approx {10}^6$ OK
• Bitmask with $n=25$: $2^{25}\approx 3.3\times {10}^7$—tight

This mental check saves you from coding a solution that TLEs.

---

Contest Cheat Sheet

+--------------------------------------------------------------------+
|                      MATH TOOLKIT QUICK REF                        |
+--------------------------------------------------------------------+
| CEIL DIV (a,b > 0):  (a + b - 1) / b                              |
| SUM 1..n:            n * (n+1) / 2       (use long long!)         |
| SUM a..b:            (b-a+1) * (a+b) / 2 (divide even part first) |
|--------------------------------------------------------------------|
| gcd(a,b):  std::gcd(a,b)     gcd(0,x) = x    gcd(0,0) = 0       |
| lcm(a,b):  a / gcd(a,b) * b  (DIVIDE FIRST to avoid overflow)    |
|--------------------------------------------------------------------|
| PRIMALITY:  trial division up to sqrt(n), skip even and mult of 3 |
|   if (n<2) false; check 2,3; then i=5, i+=6, check i and i+2     |
|--------------------------------------------------------------------|
| SIEVE:  for i in 2..sqrt(n): if prime, cross off i*i, i*i+i, ... |
|   O(n log log n) time, O(n) space, practical up to 10^7           |
| SPF SIEVE:  store smallest prime factor -> O(log n) factorization |
|--------------------------------------------------------------------|
| POWERS OF 2 RULE:  2^10 ~ 10^3                                    |
|   log2(10^6) ~ 20   log2(10^9) ~ 30   log2(10^18) ~ 60           |
|   1LL << k  for k >= 31 (avoid int overflow!)                     |
|--------------------------------------------------------------------|
| OVERFLOW TRAPS:                                                    |
|   n*(n+1) overflows int at n ~ 46340                               |
|   a*b overflows long long at a,b ~ 3*10^9                         |
|   Always: divide before multiply when possible                     |
+--------------------------------------------------------------------+

  OVERFLOW DANGER ZONES

  Operation          Danger threshold        Fix
  +-----------------------------------------------------------------+
  | n * (n+1)        | n > 46340 (int)       | use long long        |
  | n * (n+1)        | n > 3*10^9 (ll)       | divide first         |
  | a * b            | a,b > 3*10^9          | __int128 or divide   |
  | 1 << k           | k >= 31 (int)         | 1LL << k             |
  | a * b / gcd      | a*b > 9.2*10^18       | a/gcd * b            |
  +-----------------------------------------------------------------+

  QUICK SIZE CHECK:
  int max   ~  2 * 10^9
  ll max    ~  9.2 * 10^18
  n*(n+1)/2 overflows int at n ~ 46340
  n*(n+1)/2 overflows ll  at n ~ 4.3 * 10^9

---

If I Had 5 Minutes

Five things to tattoo on your forearm before a contest:

1. ceil(a/b) = (a + b - 1) / b—only for a >= 0, b > 0
2. lcm(a,b) = a / gcd(a,b) * b—divide FIRST, never a*b/gcd
3. Sieve inner loop starts at i*i—cast (long long)i*i to avoid overflow
4. n*(n+1)/2—use long long, divide the even operand first
5. 1LL << k not 1 << k—the latter is UB for k >= 31

---

Before You Code Checklist

  +------------------------------------------------------------+
  |  MATH TOOLKIT -- BEFORE YOU CODE                           |
  +------------------------------------------------------------+
  |  [ ] 1. Are ALL variables long long where needed?          |
  |         (n*(n+1) overflows int at n ~ 46340)               |
  |  [ ] 2. Am I dividing before multiplying?                  |
  |         (lcm, arithmetic sum, binomial coefficients)       |
  |  [ ] 3. Does my ceil_div assume a >= 0? Is that valid?     |
  |  [ ] 4. Did I handle n=0, n=1, and negative inputs?        |
  |  [ ] 5. Is my sieve array sized n+1, not n?                |
  +------------------------------------------------------------+

---

Common Mistakes

Every formula above has at least one trap. This section catalogs the bugs that cost WAs so you can spot them before submitting.

Ceiling Division Pitfall for Negative a

The formula (a + b - 1) / b is the most common ceiling division in CP, but it is WRONG when a is negative. Also, (a + b - 1) can overflow when a is near LLONG_MAX—cast to __int128 or use a safe variant in that case. Here is the step-by-step breakdown:

  a = -7,  b = 3
  Correct answer: ceil(-7 / 3) = ceil(-2.333...) = -2

  Using (a + b - 1) / b:
    (-7 + 3 - 1) / 3 = -5 / 3

  C++ truncates toward zero:
    -5 / 3 = -1     <--- WRONG! (should be -2)

  The +b-1 "round up" trick pushes TOWARD zero for negatives,
  when we need it to push AWAY from zero.

  Number line:
    -3    -2    -1     0     1     2     3
     |     |     |     |     |     |     |
                 ^-C++ gives this
           ^-correct ceil(-7/3) is here

WARNING: Never use (a + b - 1) / b unless you can guarantee a >= 0. In contest code, add assert(a >= 0); or use a safe variant.

Safe alternatives (all assume b > 0):

// Option 1: Guard with assert -- simplest in contest
long long ceil_div_positive(long long a, long long b) {
    assert(a >= 0 && b > 0);
    return (a + b - 1) / b;
}

// Option 2: Branch on sign of a -- handles negative a correctly
long long ceil_div_safe(long long a, long long b) {
    // b must be positive
    if (a >= 0) return (a + b - 1) / b;  // standard trick for non-negative
    else return a / b;                     // C++ truncation IS ceiling for negative/positive
}

// Option 3: Fully general -- any signs (from implementation section above)
long long ceil_div_general(long long a, long long b) {
    return a / b + (a % b != 0 && ((a ^ b) >= 0));
}

Why does a / b work when a < 0 and b > 0? C++ truncation rounds toward zero. For a negative numerator and positive denominator, "toward zero" means "toward positive infinity"—which is exactly ceiling. C++ gives you the ceiling for free in this case.

Arithmetic Sum Overflow

$n\cdot (n+1)$ overflows a 32-bit int at $n=46340$. At $n={10}^9$ it even overflows long long before you divide by 2 if you're not careful:

// BAD: 10^9 * (10^9 + 1) = ~10^18, which fits long long
// But 2*10^9 * (2*10^9 + 1) = ~4*10^18, which overflows!
long long n = 2000000000;
long long bad = n * (n + 1) / 2;   // overflow before /2

// GOOD: divide the even part first
long long good = (n % 2 == 0) ? (n / 2) * (n + 1) : n * ((n + 1) / 2);

LCM Overflow

lcm(a, b) = a * b / gcd(a, b) is mathematically correct, but a * b overflows first. Always divide before multiplying:

long long L = a / gcd(a, b) * b;  // safe: a/gcd divides evenly

When folding LCM across an array, the intermediate LCM can itself grow past ${10}^{18}$. Detect overflow or cap early. Note that a * b / gcd(a, b) overflows even when the result fits in long long—a silent bug that only surfaces on large inputs.

long long a = 1000000000000000000LL, b = 999999999999999999LL;
long long g = gcd(a, b);

// BUG: a * b overflows long long even though lcm might fit
long long bad = a * b / g;           // overflow --> garbage

// FIX: divide first -- a/g is exact since g divides a
long long good = a / g * b;          // correct

The divide-first principle visualized:

  LCM OVERFLOW -- UNSAFE vs SAFE COMPUTATION ORDER

  a = 6*10^9     b = 4*10^9     gcd = 2*10^9     lcm = 12*10^9

  UNSAFE  a * b / gcd:
  +----------+     +----------+     +--------------------+
  | a        |--*--| b        |--/--| 24*10^18           |
  | 6*10^9   |     | 4*10^9   |     | > 9.2*10^18 max    |
  +----------+     +----------+     | ** OVERFLOW **     |
                                    +--------------------+

  SAFE  a / gcd * b:
  +----------+     +----------+     +------+     +----------+     +----------+
  | a        |--/--| gcd      |---->|  3   |--*--| b        |---->| 12*10^9  |
  | 6*10^9   |     | 2*10^9   |     +------+     | 4*10^9   |     |  FITS    |
  +----------+     +----------+                   +----------+     +----------+

LCM Overflow Detection

Even with the divide-first trick (a / gcd(a,b) * b), the LCM itself can overflow long long. This happens when two large coprime numbers produce an LCM exceeding $9.2\times {10}^{18}$.

Detection: After computing a / gcd(a,b), check whether multiplying by b would overflow before doing it:

#include <bits/stdc++.h>
using namespace std;

// Returns lcm(a, b), or -1 if it overflows long long.
// Assumes a, b >= 0.
long long safe_lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    long long g = gcd(a, b);
    long long div = a / g;
    // Overflow check: if div > LLONG_MAX / b, then div * b overflows
    if (div > LLONG_MAX / b) return -1;  // overflow!
    return div * b;
}

// Fold LCM across an array with overflow detection
long long array_lcm(const vector<long long>& v) {
    long long L = 1;
    for (long long x : v) {
        // Invariant: L == lcm of all elements processed so far, or -1 if overflow
        L = safe_lcm(L, x);
        if (L == -1) return -1;  // overflow -- LCM doesn't fit in long long
    }
    return L;
}

int main() {
    cout << safe_lcm(12, 18) << "\n";                    // 36
    cout << safe_lcm(1e18, (long long)1e18 - 1) << "\n"; // -1 (overflow)

    // When you truly need the big LCM, use __int128:
    __int128 big_lcm = (__int128)1000000000000000000LL
                     / gcd(1000000000000000000LL, 999999999999999999LL)
                     * 999999999999999999LL;
    // Can't print __int128 directly -- convert to string or use a helper
}

  OVERFLOW DETECTION DECISION TREE

  a / gcd(a,b) = q
       |
       v
  q > LLONG_MAX / b ?
     /          \
   YES           NO
    |             |
    v             v
  OVERFLOW!     q * b is safe
  use __int128  return q * b
  or cap/flag

Floating-Point sqrt Is Unreliable for Integers

sqrt(n) returns a double, which has 53 bits of mantissa. For $n>2^{53}$ it can give the wrong integer, and even for smaller $n$ rounding errors can make (long long)sqrt(n) off by 1.

// SAFE integer sqrt check
long long s = sqrtl(n);
while (s * s > n) s--;
while ((s + 1) * (s + 1) <= n) s++;
// now s = floor(sqrt(n)), exactly

Sieve: Don't Start Inner Loop at $2i$

Starting the inner loop at j = 2*i wastes time—those multiples were already marked by smaller primes. Start at j = i*i. But watch for overflow: i*i can overflow int when $i>46340$.

for (int i = 2; (long long)i * i <= n; i++)  // cast to avoid overflow

Sieve Off-by-One

Sieve off-by-one. To sieve primes up to $n$, allocate is_prime[n + 1], not is_prime[n]. Forgetting the +1 means is_prime[n] is out of bounds—undefined behavior that may silently "work" locally but crash on the judge.

// BUG: sieve up to n, but vector has size n (indices 0..n-1)
vector<bool> is_prime(n, true);    // is_prime[n] is OUT OF BOUNDS
is_prime[n] = false;               // UB -- might silently "work"

// FIX: allocate n+1 elements (indices 0..n)
vector<bool> is_prime(n + 1, true);  // is_prime[n] is valid

Why Sieve Starts at i*i—Proof Sketch

This optimization is what makes the Sieve of Eratosthenes $O(n\log \log n)$ instead of $O(n\log n)$. Here's why it works:

Claim: When sieving with prime $i$, the first composite we need to mark is $i\times i$. All smaller multiples of $i$ have already been crossed off.

Proof sketch: Consider the multiple $i\times k$ where $k<i$. Since $k<i$, either:

• $k$ is prime and $k<i$, so $i\times k$ was already crossed off when we sieved with $k$, or
• $k$ is composite, so $k$ has a prime factor $p<k<i$, and $i\times k$ was already crossed off when we sieved with $p$.

In either case, $i\times k$ for $k<i$ is already marked composite. Therefore the first "new" multiple to mark is $i\times i$.

  Prime i = 7.  Which multiples need marking?

  7*2 = 14  -- already crossed by prime 2  (2*7)
  7*3 = 21  -- already crossed by prime 3  (3*7)
  7*4 = 28  -- already crossed by prime 2  (2*14)
  7*5 = 35  -- already crossed by prime 5  (5*7)
  7*6 = 42  -- already crossed by prime 2  (2*21)
  7*7 = 49  -- NOT yet crossed! First new composite for i=7.
       ^
       +--- This is why we start at i*i

Why this gives $O(n\log \log n)$: The total work is $\sum _{p\le \sqrt{n}}n/p$ over primes $p$. By Mertens' theorem, $\sum _{p\le x}1/p\approx \log \log x$, giving $O(n\log \log n)$. Without the $i^2$ optimization, starting at $2i$ adds a $\log n$ factor from the harmonic series over all integers, not just primes.

Corollary: The outer loop only runs while $i\times i\le n$, i.e., $i\le \sqrt{n}$. Primes larger than $\sqrt{n}$ never need to cross off anything—all their multiples in range were already handled.

GCD Edge Cases

• gcd(0, x) = x for all $x$ (including gcd(0, 0) = 0)
• gcd with negative values: std::gcd returns the absolute value in C++17
• Some compilers' __gcd behaves differently for negatives—prefer std::gcd

Primality: Don't Forget $n=0$ and $n=1$

Both are not prime. Also, $n=2$ is the only even prime—make sure your 6k±1 loop does not accidentally skip it. The implementation above handles these correctly.

The 1 << k Trap

int x = 1 << 31;     // undefined behavior (signed overflow)
long long y = 1 << 40; // STILL wrong: 1 is int, shift overflows before widening

long long z = 1LL << 40;  // correct

Mental Traps

Trap: "I know the formula, so I'll just plug it in." Knowing a formula is not the same as recognizing when a problem reduces to it. Many counting problems—number of pairs, triangular arrangements, contribution sums—are arithmetic series in disguise. The trap is skipping the recognition step because the formula feels "too easy."

  WRONG                         RIGHT
  +------------------+          +------------------+
  | see "count pairs"|          | see "count pairs"|
  +--------+---------+          +--------+---------+
           |                             |
           v                             v
  +------------------+          +------------------+
  | brute force      |          | n items          |
  | nested loop      |          |   each pairs w/  |
  | O(n*n)           |          |   i before it    |
  +------------------+          |  --> n*(n-1)/2   |
                                | O(1)             |
                                +------------------+

Trap: Treating gcd(0, x) as 0 instead of x. Mathematically, $gcd(0,x)=x$. This matters in accumulation patterns like g = 0; for (x : arr) g = gcd(g, x);—the identity element is 0, not 1. If you mentally model GCD as "find common factors," zero feels like it should produce zero. It does not.

  WRONG                     RIGHT
  g = 0                     g = 0
  |                         |
  v  gcd(0, 12) = 0         v  gcd(0, 12) = 12
  v  gcd(0, 18) = 0         v  gcd(12,18) = 6
  v  gcd(0, 24) = 0         v  gcd(6, 24) = 6
  |                         |
  v                         v
  result = 0  ** WRONG      result = 6  ** RIGHT

Trap: "Integer arithmetic is just real arithmetic without decimals." Order of operations matters differently over integers. In real arithmetic, $n/2\cdot (n+1)$ and $n\cdot (n+1)/2$ are identical. In integer arithmetic, dividing an odd number first truncates and loses information.

  REAL ARITHMETIC            INTEGER ARITHMETIC

  n=7   n/2 * (n+1)         n=7   n/2 * (n+1)
      = 3.5 * 8                  = 3 * 8   <-- truncated
      = 28  [ok]                 = 24  ** WRONG

  FIX: divide the EVEN operand first
  n=7   n * ((n+1)/2)
      = 7 * 4
      = 28  [ok]

The Mistake That Teaches

Debugging narrative: the silent LCM overflow.

It was Codeforces Round #782, problem C. I had to find the LCM of an array of cycle lengths and check if it exceeded ${10}^{18}$. My code looked clean:

long long L = 1;
for (int x : a) L = L / gcd(L, (long long)x) * x;
cout << L << "\n";

Passed all samples. Got WA on test 7. I stared at the code for 20 minutes. "I'm dividing first! There's no overflow!" But there was. The result of L / gcd(L, x) * x was larger than $9.2\times {10}^{18}$. I was dividing before multiplying (good), but the LCM itself did not fit in long long. No warning, no crash—just silent wraparound to a negative number.

The fix was two lines:

long long q = L / gcd(L, (long long)x);
if (q > 1e18 / x) { cout << -1; return 0; }  // LCM too big
L = q * x;

Lesson: "Divide first" prevents intermediate overflow. It does NOT prevent the result from overflowing. Always check whether the final answer fits, especially when folding LCM across an array.

---

Useful Identities Cheat Sheet

A quick reference for formulas that show up in problems. Memorize the first three; know the rest exist.

Sums

Formula	Value	When it appears
$\sum _{i=1}^{n}i$	$\frac{n(n+1)}{2}$	Counting pairs, triangular numbers
$\sum _{i=1}^n{i}^2$	$\frac{n(n+1)(2n+1)}{6}$	Geometry, expected value
$\sum _{i=1}^n{i}^3$	${\left(\frac{n(n+1)}{2}\right)}^2$	Rare, but nice identity
$\sum _{i=0}^{n-1}{r}^i$	$\frac{r^n-1}{r-1}$	Geometric series
$\sum _{i=0}^{n-1}{2}^i$	$2^n-1$	Bitmask, binary

Number Theory

Fact	Notes
Number of divisors of $n$	Usually $O(n^{1/3})$ or less. $d(n)\le 1344$ for $n\le {10}^9$
Number of primes $\le n$	$\approx n/\ln n$. Primes $\le {10}^6$: 78498. Primes $\le {10}^7$: 664579
$\text{Fibonacci}(n)\approx {\phi }^n/\sqrt{5}$	$\phi =(1+\sqrt{5})/2\approx 1.618$. $F_{45}$ overflows int, $F_{93}$ overflows long long
$\text{lcm}(1,2,\dots ,n)$	Grows as $\approx e^n$. Exceeds ${10}^{18}$ around $n=43$
Sum of divisors function $\sigma (n)$	$\sigma (p^k)=(p^{k+1}-1)/(p-1)$ for prime $p$

Powers of 2 Quick Reference

2^10  = 1024           ~ 10^3
2^16  = 65536          ~ 6.5 * 10^4
2^20  = 1048576        ~ 10^6
2^30  = 1073741824     ~ 10^9
2^32  = 4294967296     ~ 4.3 * 10^9   (unsigned int max + 1)
2^40  ~ 10^12
2^50  ~ 10^15
2^63  ~ 9.2 * 10^18    (long long max)

---

When NOT to Use This

Not every problem with numbers needs this toolkit. Knowing when to reach for something else saves you from shoehorning the wrong tool:

Situation	Why NOT this toolkit	Use instead
Modular arithmetic (${10}^9+7$)	Needs modular inverse, not just GCD	Modular Arithmetic
Large exponents ($a^b\mathrm{mod}m$)	Binary exponentiation, not trial division	Math Fundamentals
Counting combinations $(\genfrac{}{}{0ex}{}{n}{k})$	Factorials and modular inverse	Combinatorics Basics
Primality for $n>{10}^{18}$	Trial division is too slow at $O(\sqrt{n})\approx {10}^9$	Miller-Rabin (Number Theory)
Factoring many numbers $>{10}^7$	Sieve only works up to $\sim {10}^7$ in memory	Pollard's rho or segmented sieve
Floating-point arithmetic	Integer tricks don't apply	Use double/long double carefully

Rule of thumb: This toolkit handles the integer arithmetic layer—floor/ceil, divisibility, small primes. The moment you see "mod ${10}^9+7$" or $(\genfrac{}{}{0ex}{}{n}{k})$, you have graduated to the next level.

---

What Would You Do If...?

Scenario 1: "Find the minimum number of operations to make all array elements equal, where each operation adds or subtracts $d$."

Think: The differences between elements must all be divisible by $d$. Compute $g=gcd$ of all pairwise differences (equivalently, $gcd$ of abs(a[i] - a[0])). Any valid $d$ must divide $g$. The answer is the sum of abs(a[i] - target) / d for the optimal target. Use the GCD pattern.

Scenario 2: "Two flashing lights blink every $a$ and $b$ seconds. When do they first blink together?"

Think: $\text{lcm}(a,b)$. Use a / gcd(a, b) * b. If the problem has multiple lights, fold LCM across the array with overflow detection. See LCM Overflow Detection.

Scenario 3: "Given $n\le {10}^6$, for each number in $[1,n]$ output its number of prime factors."

Think: Single trial division per number would be $O(n\sqrt{n})\approx {10}^9$—too slow. Use an SPF sieve to precompute smallest prime factors in $O(n\log \log n)$, then factorize each number in $O(\log n)$. See Sieve Then Query.

---

Self-Test

Before moving on, verify you can do these without looking at the implementations above:

• [ ] Write ceil_div that handles negative a—explain why (a + b - 1) / b fails for a = -7, b = 3
• [ ] Compute lcm(10^9, 10^9 - 1) without overflow—show the divide-first pattern and explain why a * b / gcd overflows
• [ ] State the value of gcd(0, 17) and explain why the accumulation pattern g = 0; for x: g = gcd(g, x) works correctly
• [ ] Write a primality test that avoids sqrt—explain the floating-point bug for n = p*p with large p
• [ ] Given a sieve implementation, identify whether the array size should be n or n + 1 and why
• [ ] Compute the sum 1 + 2 + ... + 10^9 in C++ without overflow—which operand do you divide first and why?
• [ ] Given "distribute 10 tasks among 3 workers," produce the answer using ceiling division and verify by hand

---

Debug This Exercises

Find the bug in each snippet. Answers are below—try before peeking.

Bug 1: Ceiling Division

int n = 10, k = 3;
int groups = (n + k) / k;  // What's wrong?

Bug 2: LCM Computation

long long a = 1000000000, b = 999999937;  // both are prime
long long L = a * b / gcd(a, b);  // What's wrong?

Bug 3: Sieve

vector<bool> is_prime(n, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i * i <= n; i++)
    if (is_prime[i])
        for (int j = i * i; j <= n; j += i)  // What's wrong?
            is_prime[j] = false;

Bug 4: Arithmetic Sum

int n = 100000;
int sum = n * (n + 1) / 2;  // What's wrong?

Answers (click to reveal)

Bug 1: Should be (n + k - 1) / k, not (n + k) / k. The formula (10 + 3) / 3 = 4 happens to give the right answer here, but (6 + 3) / 3 = 3 when the correct answer is 6/3 = 2. The off-by-one makes exact multiples round up incorrectly.

Bug 2: a * b overflows long long because ${10}^9\times {10}^9\approx {10}^{18}$, which is near the limit, and gcd(a, b) = 1 since both are prime, so a * b / 1 needs the full product. Fix: a / gcd(a, b) * b—divide first.

Bug 3: Vector is sized n, so valid indices are 0..n-1. But the inner loop writes to is_prime[j] where j can equal n—out of bounds! Fix: use vector<bool> is_prime(n + 1, true).

Bug 4: n * (n + 1) is computed as int arithmetic: 100000 * 100001 = 10,000,100,000 which overflows 32-bit int (max ~2.1 billion). Fix: cast to long long first: (long long)n * (n + 1) / 2.

---

Practice Problems

#	Problem	Source	Difficulty	CF Rating	Key Idea
1	Watermelon	CF 4A	Easy	800	Divisibility check, edge case $n=2$
2	Divisibility Problem	CF 1328A	Easy	800	Ceiling division: (b - a%b) % b steps to make $a$ divisible by $b$
3	Sum of Round Numbers	CF 1352A	Easy	800	Digit decomposition, powers of 10
4	Counting Divisors	CSES	Med	~1300	SPF sieve, then factorize each query in $O(\log n)$
5	Common Divisors	CF 1203C	Med	1300	GCD of entire array, then count its divisors
6	Yet Another Broken Keyboard	CF 1272C	Med	1300	Count substrings of valid segments using $n(n+1)/2$ formula
7	T-primes	CF 230B	Med	1300	Sieve + check if $n$ is a perfect square of a prime
8	Almost Prime	CF 26A	Hard	1500	SPF sieve to count distinct prime factors

---

Rating Progression

What to expect at each level:

CF Rating	What you'll see	Key skill from this toolkit
800-1200	Basic divisibility, "is it even?", ceil division for groups	(a + b - 1) / b, n*(n+1)/2, edge cases at 0 and 1
1200-1500	GCD of arrays, simple sieve usage, overflow-prone formulas	std::gcd fold, SPF sieve, long long discipline
1500-1800	LCM overflow, recognizing arithmetic series in disguise, 6k+/-1	Overflow detection, divide-first principle, pattern recognition
1800-2100	Combining GCD/LCM with other techniques (DP, greedy), Euler's totient	This toolkit becomes a subroutine inside bigger algorithms; see Number Theory

---

Recap

Ten formulas, three rules:

• Use long long from the start (overflow hits at $n=46340$ for int).
• Divide before you multiply (lcm, arithmetic sum, binomials).
• Test at 0, 1, negative inputs, and near LLONG_MAX.

If you internalize the pattern matcher and run the Before You Code Checklist, you will avoid the vast majority of math-related WAs at the 800–1400 level.

For structured practice, work through the problems above then continue to the 1100–1400 ladder.

---

Further Reading

• cp-algorithms: Sieve of Eratosthenes—optimized sieve implementations and analysis
• cp-algorithms: Euclidean Algorithm—GCD, extended GCD, and applications
• Codeforces Blog: Integer Overflow in C++—common overflow traps
• See: Number Theory—modular inverse, Euler's totient, Fermat's little theorem
• See: Math Fundamentals—modular arithmetic patterns, exponentiation
• See: Combinatorics Basics—binomial coefficients, counting techniques
• See: Bit Manipulation—1LL << k, __builtin_ctzll, powers of 2 tricks
• See: Complexity Analysis—validating $O(n\log \log n)$ sieve bounds
• See: Debugging and Stress Testing—stress-testing math edge cases
• See: Essential Techniques—greedy, binary search, and two pointers often combine with math
• See: Data Structure Selection Guide—when the bottleneck is storage, not arithmetic

---

Next Up: Modular Arithmetic Basics—when problems say "output the answer modulo ${10}^9+7$," you will need modular inverse, fast exponentiation, and the tools from this file as building blocks.