Modular Arithmetic
Authors: Darren Yao, Michael Cao, Andi Qu, Benjamin Qi, Andrew Wang
Contributors: Kevin Sheng, Mihnea Brebenel
Working with remainders from division.
Prerequisites
Resources | ||||
---|---|---|---|---|
AryanshS | introduces modular arithmetic through numerous math-contest-level examples and problems | |||
IUSACO | very brief, module is based off this | |||
David Altizio | plenty of examples from math contests | |||
CPH | ||||
PAPS | ||||
CF | some practice probs | |||
MONT |
Introduction
In modular arithmetic, instead of working with integers themselves, we work with their remainders when divided by . We call this taking modulo . For example, if we take , then instead of working with , we use . Usually, will be a large prime, given in the problem; the two most common values are and . Modular arithmetic is used to avoid dealing with numbers that overflow built-in data types, because we can take remainders, according to the following formulas:
Modular Exponentiation
Focus Problem – try your best to solve this problem before continuing!
Resources
Resources | ||||
---|---|---|---|---|
cp-algo |
Binary exponentiation can be used to efficently compute . To do this, let's break down into binary components. For example, = = . Then, if we know for all which are powers of two (, , , , , we can compute in .
To deal with , observe that modulo doesn't affect multiplications, so we can directly implement the above "binary exponentiation" algorithm while adding a line to take results .
Solution - Exponentiation
#include <bits/stdc++.h>using namespace std;using ll = long long;ll exp(ll x, ll n, ll m) {assert(n >= 0);x %= m; // note: m * m must be less than 2^63 to avoid ll overflowll res = 1;while (n > 0) {
Modular Inverse
The modular inverse is the equivalent of the reciprocal in real-number arithmetic; to divide by , multiply by the modular inverse of . We'll only consider prime moduli here.
For example, the inverse of modulo is . This means that for any integer ,
For example, .
Resources | ||||
---|---|---|---|---|
cp-algo | Various ways to take modular inverse, we'll only discuss the second here |
With Exponentiation
Fermat's Little Theorem (not to be confused with Fermat's Last Theorem) states that all integers not divisible by satisfy . Consequently, . Therefore, is a modular inverse of modulo .
const int MOD = 1e9 + 7;int main() {ll x = exp(2, MOD - 2, MOD);cout << x << "\n"; // 500000004assert(2 * x % MOD == 1);}
With Euclidean Division
We can also find modular inverses through Euclidean Division. Given the prime modulus we have: , where k = and . Then: .
Here is a short recursive implementation of the above formula:
int inv(int x) { return x <= 1 ? x : MOD - MOD / x * inv(MOD % x) % MOD; }
The advantage of this approach is that we can precompute the inverse modular of numbers in the range in .
inv[1] = 1; // assume we already defined this arrayfor (int i = 2; i < MOD; i++) { inv[i] = MOD - MOD / i * inv[MOD % i] % MOD; }
Because it takes time to compute a modular inverse modulo , frequent use of division inside a loop can significantly increase the running time of a program. If the modular inverse of the same number(s) is/are being used many times, it is a good idea to precalculate it.
Also, one must always ensure that they do not attempt to divide by 0. Be aware that after applying modulo, a nonzero number can become zero, so be very careful when dividing by non-constant values.
Optional: Another Way to Compute Modular Inverses
We can also use the extended Euclidean algorithm. See the module in the Advanced section.
Templates
Here are some templates that implement integer types that automatically wrap around when they exceed a certain modulus:
Resources | ||||
---|---|---|---|---|
Benq | ||||
Benq | feasible to type up during a contest | |||
AtCoder | contains a | |||
AtCoder |
Here's an example using Benq's template:
#include <bits/stdc++.h>using namespace std;const int MOD = 1e9 + 7;Code Snippet: ModInt (Click to expand)int main() {{int a = 1e8, b = 1e8, c = 1e8;
And one using AtCoder's:
#include <bits/stdc++.h>using namespace std;// https://atcoder.github.io/ac-library/document_en/modint.html// (included in atcoder grading)#include <atcoder/modint>using mint = atcoder::modint;const int MOD = 1e9 + 7;
Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CSES | Easy | Show TagsModular Arithmetic | |||
CF | Easy | Show TagsModular Arithmetic | |||
Kilonova | Normal | Show TagsMath, Prime Factorization | |||
YS | Normal | Show TagsModular Arithmetic | |||
CSES | Normal | Show TagsModular Arithmetic |
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!