Modular Arithmetic Basics

The Modulo Operator

a % m gives the remainder when a is divided by m. The key rules:

(a + b) % M = ((a % M) + (b % M)) % M
(a * b) % M = ((a % M) * (b % M)) % M
(a - b) % M = ((a % M) - (b % M) + M) % M  // add M to avoid negative

const long long MOD = 1e9 + 7;

long long add_mod(long long a, long long b) {
    return (a % MOD + b % MOD) % MOD;
}

long long mul_mod(long long a, long long b) {
    return (a % MOD) * (b % MOD) % MOD;
}

long long sub_mod(long long a, long long b) {
    return ((a % MOD) - (b % MOD) + MOD) % MOD;
}

const MOD: u64 = 1_000_000_007;

fn add_mod(a: u64, b: u64) -> u64 {
    (a % MOD + b % MOD) % MOD
}

fn mul_mod(a: u64, b: u64) -> u64 {
    (a % MOD) * (b % MOD) % MOD
}

fn sub_mod(a: u64, b: u64) -> u64 {
    (a % MOD + MOD - b % MOD) % MOD
}

Problem: Large Sum

Given N and N integers, print the sum modulo 10⁹+7. The values can be up to 10¹², so a 64-bit sum works but the problem wants the result modulo M.

const long long MOD = 1e9 + 7;

int main() {
    int n; cin >> n;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        long long x; cin >> x;
        sum = (sum + x % MOD) % MOD;
    }
    cout << sum << "\n";
    return 0;
}

const MOD: u64 = 1_000_000_007;

fn main() {
    // ... read nums ...
    let sum = nums.iter().fold(0, |acc, &x| (acc + x % MOD) % MOD);
    println!("{}", sum);
}

Key Takeaways

• → Apply % M after every addition and multiplication.
• → Subtraction: add M before the final modulo to avoid negatives.
• → Use long long / u64 — multiplication of two mod values < M still fits in 64 bits.

Practice

• Kattis: Modular Arithmetic
• Codeforces 598A: Tricky Sum
• AtCoder ABC 146 B: ROT N