Unit 2: Basic math operations (addition, subtraction, multiplication, division and exponentiation)

Competitive coding treats the four arithmetic operations plus exponentiation not as trivial primitives but as operations that must survive overflow, run in logarithmic time, and behave correctly under a modulus. This unit builds the modular toolkit, the fast-exponentiation idea, and two counting principles that turn brute force into arithmetic.

I. Orientation — Modular arithmetic and its ground rules

Almost every problem here lives in a ring of residues modulo some prime, usually M = 1e9 + 7, chosen because it is prime, fits in 32 bits, and keeps products within 64-bit range after reduction.

• Congruence: a ≡ b (mod M) means M | (a − b); every integer maps to a residue in [0, M−1].
• Distributes over +, −, ×: (a op b) mod M = ((a mod M) op (b mod M)) mod M for addition, subtraction and multiplication.
• Division is not native: you cannot reduce a / b term by term; division is replaced by multiplication with a modular inverse (Section V).
• Overflow is the enemy: two residues below 1e9+7 multiply to nearly 1e18, which fits in a signed 64-bit long long but not in 32 bits — the reason fast modulo multiplication (Section II) exists.
• Negative fix-up: after subtraction write ((a − b) % M + M) % M to keep the result non-negative.

II. Fast modulo multiplication

The point of this section is computing (a × b) mod M when a × b overflows the widest available integer type.

A. The overflow problem

• When it bites: if M ≈ 1e18, then a, b can each be near 1e18 and their product near 1e36, far beyond 64 bits.
• Goal: obtain the exact residue without a 128-bit product.

B. Fast modulo multiplication by doubling

• Principle: treat multiplication as repeated doubling, mirroring binary exponentiation but with + instead of ×.
• Invariant: accumulate a into the result whenever the current bit of b is set, doubling a each step, reducing mod M throughout so no value exceeds 2M.

mulmod(a, b, M):
    result = 0
    a %= M
    while b > 0:
        if b & 1: result = (result + a) % M
        a = (a * 2) % M      # only a+a, never a*b
        b >>= 1
    return result

• Complexity: O(log b) additions, each safe because result + a < 2M.
• Symbols: a, b operands; M modulus; result running sum of selected doublings.
• Alternative: where available, cast to __int128 and reduce directly — faster but non-portable.

III. Exponential squaring

This section computes a^n in O(log n) multiplications instead of O(n).

A. Binary exponentiation (exponentiation by squaring)

• Idea: write n in binary; a^n is the product of a^(2^k) over set bits, and each squared power is obtained from the previous by one squaring.
• Recurrence: a^n = (a^(n/2))^2 if n even, = a · (a^((n−1)/2))^2 if n odd.

power(a, n):
    result = 1
    while n > 0:
        if n & 1: result = result * a
        a = a * a
        n >>= 1
    return result

• Symbols: a base, n non-negative exponent, result accumulated product.
• Worked example: 3^13, with 13 = 1101₂. Squarings give 3, 9, 81, 6561; multiply those for bits 1,3,4 → 3 · 81 · 6561 = 1594323 = 3^13.
• Reuse: the same skeleton drives matrix exponentiation and modular exponentiation.

IV. N-th non-square number

This section finds the N-th positive integer that is not a perfect square without listing squares.

A. Direct formula

• Observation: below or equal to k there are ⌊√k⌋ perfect squares, so the count of non-squares up to k is k − ⌊√k⌋.
• Closed form: the N-th non-square is
  
  TEXT

  ans = N + floor(0.5 + sqrt(N))

• Why the correction term: round(√N) equals the number of squares that have been "skipped" by position N, so adding it shifts past exactly those squares.
• Symbols: N the requested index (1-based); ans the resulting non-square.
• Worked example: N = 5 → round(√5) = 2, so ans = 7; the non-squares are 2,3,5,6,7,… and the 5th is indeed 7.
• Care: use integer-safe rounding to avoid floating-point error near perfect squares.

V. Modular arithmetic under exponentiation and division

This section applies the fast-power idea inside a modulus and defines division there.

A. Modular Exponentiation

• Statement: compute a^n mod M where n may be as large as 1e18.
• Method: binary exponentiation with a reduction after every multiply.

powmod(a, n, M):
    result = 1
    a %= M
    while n > 0:
        if n & 1: result = result * a % M
        a = a * a % M
        n >>= 1
    return result

• Complexity: O(log n) multiplications, each safe if M fits in 32 bits (products stay under 1e18).
• Symbols: M modulus; other symbols as in Section III.

B. Modular multiplicative inverse

• Definition: the inverse of a modulo M is x with a·x ≡ 1 (mod M); it replaces division since a/b mod M = a · b⁻¹ mod M.
• Existence: exists iff gcd(a, M) = 1.
• Two routes, contrasted:
  1. Fermat's little theorem (M prime): since a^(M−1) ≡ 1, the inverse is a^(M−2) mod M, one call to powmod. Simple, requires a prime modulus.
  2. Extended Euclidean (M any coprime modulus): solve a·x + M·y = 1 and take x mod M. Works for composite M, needs no primality.
• Worked example: inverse of 3 mod 7: 3^(7−2) = 3^5 = 243 ≡ 5 (mod 7), and 3·5 = 15 ≡ 1.

VI. Sum of middle row and element in matrix

This section reads the centre of a square matrix of odd order.

A. Middle row and middle element

• Precondition: the matrix is n × n with n odd, so a unique middle index mid = n / 2 (integer division) exists.
• Middle row sum: add every element of row mid: Σ mat[mid][j] for j = 0 … n−1.
• Middle element: the single central entry mat[mid][mid].
• Complexity: O(n) for the row, O(1) for the element; no full traversal needed.
• Worked example: for the 3×3 matrix rows [1,2,3],[4,5,6],[7,8,9], mid = 1, middle-row sum = 15, middle element = 5.

VII. Checking if all rows of a matrix are circular rotations of each other

This section decides whether every row is some cyclic shift of the first row.

A. Concatenation-and-search test

• Key fact: string B is a circular rotation of string A iff B is a substring of A + A.
• Procedure: join the first row into a string S, form S + S, then check that every other row (also joined) appears as a substring.

row0 = concat(mat[0])
doubled = row0 + row0
for i in 1..n-1:
    if concat(mat[i]) not substring of doubled: return false
return true

• Complexity: naive substring check gives O(n²·m) for n rows of length m; KMP reduces each search to O(m).
• Basis: A+A contains every rotation of A as a length-|A| window, so substring membership is exactly the rotation test.

VIII. Inclusion–Exclusion Principle

This section counts the size of a union by alternately adding and subtracting intersections.

A. Statement and formula

• Two sets: |A ∪ B| = |A| + |B| − |A ∩ B|.
• General form:
  
  TEXT

  |A₁ ∪ … ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| − … ± |A₁∩…∩Aₙ|

• Sign rule: a k-fold intersection carries sign (−1)^(k+1), cancelling the over-counting of earlier terms.
• Implementation: iterate over all 2ⁿ − 1 non-empty subsets via bitmasks; add or subtract by popcount parity.

B. Applications and limitations

• Typical use: counting integers in [1, N] divisible by at least one of several primes — subtract pairwise LCM-multiples, add triple-wise, and so on.
• Worked example: count of numbers ≤ 30 divisible by 2 or 3: 15 + 10 − 5 = 20.
• Limitation: the 2ⁿ subset enumeration is only feasible for small n (roughly n ≤ 20).

IX. Pigeonhole principle

This section guarantees a collision when items outnumber containers.

A. Statement and consequences

• Basic form: placing n items into m boxes with n > m forces at least one box to hold ≥ 2 items.
• Generalised form: some box holds at least ⌈n / m⌉ items.
• Existence, not construction: it proves a repetition or clash must occur without locating it.

B. Uses in coding

• Duplicate detection: among any M+1 integers, two share a residue mod M, so their difference is divisible by M.
• Subarray sums: among prefix sums P₀ … Pₙ there are n+1 values but only n residues mod n, so two prefix sums are congruent — giving a contiguous subarray whose sum is divisible by n.
• Bounding arguments: it caps how large a "distinct" collection can be before a forced repeat, pruning search spaces.