Modular Arithmetic for DSA

Quick Reference#

The whole page on one screen. Everything here is unpacked in full below. Watch for the marked lines: ★ trick · ⚠ pitfall · 💡 tip.

Detailed Walkthrough#

The trap. Your logic is right and the small cases pass, but on a big case the answer comes out negative — garbage where you expected trillions. Nothing in the logic is wrong. The true answer had hundreds of digits, a long holds ~19, and it silently wrapped around. That's why the problem says "print the answer modulo 10⁹+7": it hands you the one tool that keeps every intermediate value inside the box. The five habits below are the whole survival kit — each is just a way to reduce early and never let a value grow too large.

1. What "mod" actually is, and why problems ask for it#

The modulo of a number is simply the remainder left over after division. 17 % 5 = 2, because 17 = 3×5 + 2.

The clock analogy. A 12-hour clock is arithmetic mod 12. It's 10 o'clock, you add 5 hours — not 15 o'clock, it's 3. The clock silently did 15 % 12 = 3. Every value on the face lives in 0..11 no matter how much time you add. Modular arithmetic is exactly this: a number line rolled into a circle of size m, where everything stays inside 0 .. m-1.

When a problem ends with "return the answer modulo 10⁹+7," it's telling you the true count is astronomically large — think number of ways to arrange things, which explodes factorially. Nobody can store or check a 100-digit number, so everyone compares just the remainder mod a fixed prime. If your remainder matches theirs, your logic was right.

2. int vs long, and the L suffix#

Overflow is the whole game, so the first move is knowing exactly how much room each type gives you and typing the wide one on purpose. Anything that could grow past a couple billion goes in a long from the start — not an int you widen later.

3. Why that exact number, and the "sweet spot"#

10⁹+7 is often called a "sweet spot." Two properties earn it that name.

When you hit a modulo problem, run these#

Rule 1Use long everywhere#

The first defense is to never touch a 32-bit int for values that could grow. Declare the modulus and every running value as long from the start, so nothing has a chance to overflow before you reduce it.

long MOD = 1_000_000_007L;   // modulus as a long constant
long ans = 0, prod = 1;    // running values are long, not int

Rule 2Take two at a time#

Never combine three or more factors before reducing. Multiply two, take % M, then bring in the next one.

Here's the danger: in (a * b * c) % M, the product a * b may already have overflowed before the * c or the % M ever runs. The modulo can't rescue a value that's already garbage. So fold in one factor at a time, reducing after each step.

// Rule 2 in Java: fold in one factor at a time
long temp = (a % MOD) * (b % MOD) % MOD;   // two at a time
temp = temp * (c % MOD) % MOD;             // then the third

The properties this rests on#

Mod distributes over +, −, and × — reducing early only discards whole multiples of M, which never affect a remainder. That's why "two at a time" is legal.

Rule 3Never use Math.pow() — binary exponentiation#

Math.pow() returns a double, which can't hold a large integer exactly and gives you no way to reduce mod M partway through. So (long) Math.pow(a, b) % MOD silently returns wrong answers for large exponents — rounding error, plus the value overflows before the modulo ever runs. The fix is to write the power yourself.

The naive fix is a loop — multiply a into the answer b times, reducing each step. That's O(b), too slow when b is up to 109.

// O(b) - correct but too slow for large b
long ans = 1;
for (int i = 0; i < b; i++) ans = ans * a % MOD;

Binary exponentiation computes ab % M in O(log b) by squaring the base and halving the exponent — because ab = (ab/2)2 when b is even, and you peel off one factor when b is odd.

Recursive version#

The recursive form reads exactly like the math: base case b == 0 returns 1, an odd b peels off one factor, an even b squares the half.

static long MOD = 1_000_000_007L;

static long binpow(long a, long b) {
    if (b == 0) return 1;              // base case
    if ((b & 1) == 1)                    // b is odd
    return a % MOD * binpow(a, b - 1) % MOD;
    long temp = binpow(a, b / 2);        // b is even
    return temp * temp % MOD;
}

Iterative version (preferred in Java — no stack risk)#

static long power(long a, long b) {
    a %= MOD;
    long res = 1;
    while (b > 0) {
        if ((b & 1) == 1) res = res * a % MOD;  // bit set → multiply in
        a = a * a % MOD;                        // square the base
        b >>= 1;                                 // next bit
    }
    return res;
}

Rule 4In modulo you don't divide — you take the inverse #

Plain division breaks under a modulus: (12 / 6) % 10 = 2, but reducing first gives (12%10) / (6%10) = 2/6, which isn't even an integer. Remainders throw away the information division needs.

To divide by b under a modulus, multiply by b's modular inverse — the number that plays the role of 1/b, i.e. the x with (b · x) % M = 1.

A concrete example: find x so that (6 · x) % 7 = 1. Testing, 6 · 6 = 36, and 36 % 7 = 1 — so 6-1 = 6 under mod 7. Dividing by 6 becomes multiplying by 6. But guessing doesn't scale, which is where Fermat comes in.

The key formula is exactly this last step: the inverse of any a is aM-2, which you already know how to compute fast with binary exponentiation. So inv is a one-liner on top of power.

// modular inverse via Fermat (MOD must be prime)
static long inv(long x) {
    return power(x, MOD - 2);      // x^(M-2) % M  ==  x^-1
}
// then:  (a / b) % M   becomes   a * inv(b) % MOD

Rule 5Fix negatives when printing#

The % operator can return a negative result when the left side is negative: -3 % 7 gives -3, not the mathematically clean 4. A negative remainder fails comparisons and corrupts later steps — and it's how a "correct" solution ends up printing a negative final answer.

// Rule 5 - the guaranteed-positive print
System.out.println(((ans % MOD) + MOD) % MOD);

Small moves that keep the logic clean#

The n(n+1)/2 trap#

The sum 1 + 2 + ... + n = n(n+1)/2. The final answer fits fine, but the intermediate product n * (n+1) can overflow before you divide by 2. For n ≈ 3×109, n(n+1) already blows past a long.

static long tri(long n) {
    return (n % 2 == 0) ? (n / 2) * (n + 1) : n * ((n + 1) / 2);
}

Reaching the next multiple of k#

x % k is how far past the last multiple of k you are, so k - (x % k) is the gap to the next one. If x is already a multiple that gives k (wrong — should be 0), so one outer % k fixes the edge case.

Divide and remainder, read as a pair#

The same two operators keep showing up as a clean way to think, not just to compute. For any x and a block size k: x / k tells you which block you're in and x % k tells you where inside it. Almost every "wrap it around", "which bucket", "flatten a grid", or "peel a digit" question is just this one idea in disguise.

All 5 rules in one expression#

Compute Ans = (A + ((B − C)D) / (E × 100) − F × G) % (109+7), given 1 ≤ A..G ≤ 109. If the answer is a fraction P/Q, print P · Q-1 % M.

This is the capstone — every rule fires at once. Read it as a pipeline of temp values, each reduced immediately (Rule 2), powers via binary expo (Rule 3), the division as a multiply-by-inverse (Rule 4), and a final positive-print (Rule 5).

import java.util.Scanner;

public class Main {
    static long MOD = 1_000_000_007L;

    static long power(long a, long b) {
        a %= MOD; long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD; b >>= 1;
        }
        return res;
    }
    static long inv(long x) { return power(x, MOD - 2); }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong(), b = sc.nextLong(), c = sc.nextLong();
        long d = sc.nextLong(), e = sc.nextLong();
        long f = sc.nextLong(), g = sc.nextLong();

        long t  = ((b - c) % MOD + MOD) % MOD;   // (B-C), guard negative
        t = power(t, d);                        // (B-C)^D  (Rule 3)
        long t2 = (e % MOD) * 100 % MOD;         // E*100    (Rule 2)
        t = t * inv(t2) % MOD;                  // / (E*100) (Rule 4)
        t2 = f % MOD * (g % MOD) % MOD;         // F*G      (Rule 2)
        t = (a + t) % MOD;                      // + A
        t = (t - t2) % MOD;                     // - F*G
        System.out.println(((t % MOD) + MOD) % MOD);  // Rule 5
    }
}

Geometric series sum, mod M#

Compute F(x, n, m) = (1 + x + x2 + ... + xn) % m, with 1 ≤ x, n, m ≤ 109.

Summing term-by-term is O(n) — too slow. Notice this is a geometric progression (GP) with first term 1 and ratio x, so the closed form applies:

Now every rule shows up: the numerator's power needs binary expo (Rule 3), the −1 can go negative (Rule 5), and the division by (x−1) is a multiply-by-inverse (Rule 4). Two edge cases matter.

Case 1 — m is prime (Fermat inverse works)#

static long gpSumPrime(long x, long n, long m) {
    MOD = m;                                  // power/inv use MOD
    if (x == 1) return (n + 1) % m;         // edge case (1)
    long num = ((power(x, n + 1) - 1) % m + m) % m;  // x^(n+1) - 1, guarded
    long den = ((x - 1) % m + m) % m;          // x - 1, guarded
    long ans = num * inv(den) % m;            // / (x-1) via inverse
    return ((ans % m) + m) % m;               // Rule 5
}

Case 2 — m is not prime#

When you can't invert, avoid division entirely. Split the series in halves. For an even count of terms, S(k terms) = S(k/2) × (1 + xk/2); for odd, peel one term. This is O(log n) and uses only + and ×, so any modulus (prime or not) is fine.

// sum of 1 + x + ... + x^(cnt-1), i.e. cnt terms, mod m. No inverse needed.
static long gpTerms(long x, long cnt, long m) {
    if (cnt == 0) return 0;
    if (cnt == 1) return 1 % m;
    if ((cnt & 1) == 0) {                       // even: pair up the halves
        long half = gpTerms(x, cnt / 2, m);
        long factor = (1 + powMod(x, cnt / 2, m)) % m;
        return half * factor % m;
    } else {                                    // odd: last term + the rest
        return (gpTerms(x, cnt - 1, m) + powMod(x, cnt - 1, m)) % m;
    }
}
// call with cnt = n + 1 terms:  gpTerms(x, n + 1, m)
// powMod is binary exponentiation taking an explicit modulus m

How to decide what to do#

Open a problem and run this top to bottom — it's the 5 rules as a checklist.

Interview / Practice Q&A#

Click to reveal. Answers sized to read aloud.

Key Takeaways#

The through-line. Every rule here is one defense against the same enemy — a value growing past what a long can hold before you reduce it. Reduce early, square instead of looping, invert instead of dividing, and guard the sign on the way out. Once those become reflexes, modular problems stop being about arithmetic and start being about logic.