Modular Arithmetic for Competitive Programming
In mathematics, modular arithmetic refers to the arithmetic of integers that wraps around when a certain value is reached, called the modulus. This becomes particularly crucial when handling large numbers in competitive programming. This article “Modular Arithmetic for Competitive Programming” will explore modular arithmetic, its operations, the underlying concepts, and practical applications. By understanding and implementing modular arithmetic, programmers can effectively manage and manipulate large integers, enhancing their skills in competitive programming.
Table of Content
- What is Modular Arithmetic?
- Modular Arithmetic Operations
- Idea behind Modular Arithmetic
- Implementation of Modular Arithmetic
- Use Cases of Modular arithmetic in Competitive Programming
- Practice Problems on Modular Arithmetic for CP
What is Modular Arithmetic?
Modular arithmetic is a branch of arithmetic mathematics related to the “mod” functionality. It is a system of arithmetic for integers, where numbers “wrap around” upon reaching a certain value, known as the modulus. In its most elementary form, it is arithmetic done with a count that resets itself to zero every time a certain whole number N greater than one, known as the modulus (mod), has been reached.
Modular Arithmetic Operations
The implementation of modular arithmetic involves various operations such as addition, subtraction, multiplication, division, and exponentiation. Here are some rules for these operations:
- Modular Addition: (a + b) mod m = ((a mod m) + (b mod m)) mod m1.
- Modular Subtraction: The same rule as modular addition applies.
- Modular Multiplication: (a * b) mod m = ((a mod m) * (b mod m)) mod m1.
- Modular Division: (a / b) mod m = (a * (inverse of b if exists)) mod m1. The modular inverse of a mod m exists only if a and m are relatively prime i.e., gcd(a, m) = 1.
- Modular Exponentiation: Finding a^b mod m is the modular exponentiation.
Idea behind Modular Arithmetic:
The concept of modular arithmetic is to find the remainder of a number upon division by another number. For example, if we have “A mod B” and we increase ‘A‘ by a multiple of ‘B‘, we will end up in the same spot, i.e.,”A mod B = (A + K * B) mod B” for any integer ‘K‘.
Visualizing the Idea behind Modular Arithmetic:
To visualize the modulo operator, we can use circles. We write 0 at the top of a circle and continuing clockwise writing integers 1, 2, … up to one less than the modulus. For example, a clock with the 12 replaced by a 0 would be the circle for a modulus of 12.
To find the result of “A mod B” we can follow these steps:
- Construct this clock for size ‘B’.
- Start at 0 and move around the clock ‘A’ steps.
- Wherever we land is our solution. (If the number is positive we step clockwise, if it’s negative we step counter-clockwise.)
Here are some examples of modular arithmetic operations:
- 8 mod 4 = 0: With a modulus of 4 we make a clock with numbers 0, 1, 2, 3. We start at 0 and go through 8 numbers in a clockwise sequence 1, 2, 3, 0. We ended up at 0 so 8 mod 4 = 0.
- 7 mod 2 = 1: With a modulus of 2 we make a clock with numbers 0, 1. We start at 0 and go through 7 numbers in a clockwise sequence 1, 0, 1, 0, 1, 0, 1. We ended up at 1 so 7 mod 2 = 1.
- -5 mod 3 = 1: With a modulus of 3 we make a clock with numbers 0, 1, 2. We start at 0 and go through 5 numbers in counter-clockwise sequence (5 is negative) 2, 1, 0, 2, 1. We ended up at 1 so -5 mod 3 = 1.
Implementation of Modular Arithmetic
Below code performs modular addition, subtraction, multiplication, and division.
C++
#include <bits/stdc++.h> using namespace std; // Function to perform Modular Addition int modAdd( int a, int b, int m) { return ((a % m) + (b % m)) % m; } // Function to perform Modular Subtraction int modSub( int a, int b, int m) { return ((a % m) - (b % m) + m) % m; // Adding m to handle negative numbers } // Function to perform Modular Multiplication int modMul( int a, int b, int m) { return ((a % m) * (b % m)) % m; } // Function to calculate power of a number int power( int x, unsigned int y, int p) { int res = 1; x = x % p; if (x == 0) return 0; while (y > 0) { if (y & 1) res = (res * x) % p; y = y >> 1; x = (x * x) % p; } return res; } // Function to find modular inverse of a under modulo m // Assumption: m is prime int modInverse( int a, int m) { return power(a, m - 2, m); } // Function to perform Modular Division int modDiv( int a, int b, int m) { a = a % m; int inv = modInverse(b, m); return (inv * a) % m; } int main() { int a = 10, b = 20, m = 7; cout << "Modular Addition: " << modAdd(a, b, m) << endl; cout << "Modular Subtraction: " << modSub(a, b, m) << endl; cout << "Modular Multiplication: " << modMul(a, b, m) << endl; cout << "Modular Division: " << modDiv(a, b, m) << endl; return 0; } |
Java
class GFG { // Function to perform Modular Addition static int modAdd( int a, int b, int m) { return ((a % m) + (b % m)) % m; } // Function to perform Modular Subtraction static int modSub( int a, int b, int m) { return ((a % m) - (b % m) + m) % m; // Adding m to handle negative numbers } // Function to perform Modular Multiplication static int modMul( int a, int b, int m) { return ((a % m) * (b % m)) % m; } // Function to calculate power of a number static int power( int x, int y, int p) { int res = 1 ; x = x % p; if (x == 0 ) return 0 ; while (y > 0 ) { if ((y & 1 ) == 1 ) res = (res * x) % p; y = y >> 1 ; x = (x * x) % p; } return res; } // Function to find modular inverse of a under modulo m // Assumption: m is prime static int modInverse( int a, int m) { return power(a, m - 2 , m); } // Function to perform Modular Division static int modDiv( int a, int b, int m) { a = a % m; int inv = modInverse(b, m); return (inv * a) % m; } public static void main(String[] args) { int a = 10 , b = 20 , m = 7 ; System.out.println( "Modular Addition: " + modAdd(a, b, m)); System.out.println( "Modular Subtraction: " + modSub(a, b, m)); System.out.println( "Modular Multiplication: " + modMul(a, b, m)); System.out.println( "Modular Division: " + modDiv(a, b, m)); } } // This code is contributed by ragul21 |
C#
using System; class Program { // Function to perform Modular Addition static int ModAdd( int a, int b, int m) { return ((a % m) + (b % m)) % m; } // Function to perform Modular Subtraction static int ModSub( int a, int b, int m) { return ((a % m) - (b % m) + m) % m; } // Function to perform Modular Multiplication static int ModMul( int a, int b, int m) { return ((a % m) * (b % m)) % m; } // Function to calculate power of a number static int Power( int x, uint y, int p) { int res = 1; x = x % p; if (x == 0) return 0; while (y > 0) { if ((y & 1) == 1) res = (res * x) % p; y = y >> 1; x = (x * x) % p; } return res; } // Function to find modular inverse of a under modulo m // Assumption: m is prime static int ModInverse( int a, int m) { return Power(a, ( uint )(m - 2), m); } // Function to perform Modular Division static int ModDiv( int a, int b, int m) { a = a % m; int inv = ModInverse(b, m); return (inv * a) % m; } static void Main() { int a = 10, b = 20, m = 7; Console.WriteLine( "Modular Addition: " + ModAdd(a, b, m)); Console.WriteLine( "Modular Subtraction: " + ModSub(a, b, m)); Console.WriteLine( "Modular Multiplication: " + ModMul(a, b, m)); Console.WriteLine( "Modular Division: " + ModDiv(a, b, m)); } } // This code is contributed by shivamgupta310570 |
Javascript
// Function to perform Modular Addition function modAdd(a, b, m) { return ((a % m) + (b % m) + m) % m; // Adding m to handle negative numbers } // Function to perform Modular Subtraction function modSub(a, b, m) { return ((a % m) - (b % m) + m) % m; // Adding m to handle negative numbers } // Function to perform Modular Multiplication function modMul(a, b, m) { return ((a % m) * (b % m) + m) % m; // Adding m to handle negative numbers } // Function to calculate power of a number function power(x, y, p) { let res = 1; x = x % p; if (x === 0) return 0; while (y > 0) { if (y & 1) res = (res * x) % p; y = y >> 1; x = (x * x) % p; } return res; } // Function to find modular inverse of a under modulo m // Assumption: m is prime function modInverse(a, m) { return power(a, m - 2, m); } // Function to perform Modular Division function modDiv(a, b, m) { a = a % m; let inv = modInverse(b, m); return (inv * a) % m; } // Example usage let a = 10, b = 20, m = 7; console.log( "Modular Addition:" , modAdd(a, b, m)); console.log( "Modular Subtraction:" , modSub(a, b, m)); console.log( "Modular Multiplication:" , modMul(a, b, m)); console.log( "Modular Division:" , modDiv(a, b, m)); // This code is contributed by shivamgupta310570 |
Python3
# Function to perform Modular Addition def mod_add(a, b, m): return (a % m + b % m) % m # Function to perform Modular Subtraction def mod_sub(a, b, m): return ((a % m) - (b % m) + m) % m # Function to perform Modular Multiplication def mod_mul(a, b, m): return (a % m * b % m) % m # Function to calculate power of a number def power(x, y, p): res = 1 x = x % p if x = = 0 : return 0 while y > 0 : if y & 1 : res = (res * x) % p y = y >> 1 x = (x * x) % p return res # Function to find modular inverse of a under modulo m # Assumption: m is prime def mod_inverse(a, m): return power(a, m - 2 , m) # Function to perform Modular Division def mod_div(a, b, m): a = a % m inv = mod_inverse(b, m) return (inv * a) % m if __name__ = = "__main__" : a, b, m = 10 , 20 , 7 print ( "Modular Addition:" , mod_add(a, b, m)) print ( "Modular Subtraction:" , mod_sub(a, b, m)) print ( "Modular Multiplication:" , mod_mul(a, b, m)) print ( "Modular Division:" , mod_div(a, b, m)) # This code is contributed by shivamgupta0987654321 |
Modular Addition: 2 Modular Subtraction: 4 Modular Multiplication: 4 Modular Division: 4
Use Cases of Modular arithmetic in Competitive Programming:
Modular arithmetic is commanly used in competitive programming and coding contests that require us to calculate the mod of something. It is typically used in combinatorial and probability tasks, where you are asked to calculate a huge number, then told to output it modulo 10^9 + 7. Below are the more use cases of modular arithmetic in CP.
1. Modular arithmetic in Combinatorial Tasks:
In combinatorial tasks, you are often asked to calculate a huge number, then told to output it modulo 10^9 + 7. This is because the number can be so large that it cannot be stored in a variable of any data type. By taking the mod of the number, we reduce its size to a manageable level.
2. Modular arithmetic in Polynomial Arithmetic:
Modular arithmetic is used in polynomial arithmetic to perform addition, subtraction, and multiplication of polynomials under a modulus
3. Modular arithmetic in Hashing Algorithms:
Many hashing algorithms use modular arithmetic to ensure that the hash values they produce fit into a certain range.
4. Modular arithmetic in Probability Tasks:
In probability tasks, you might need to calculate the probability of an event occurring. The probability can be a huge number, and you are often asked to output it modulo 10^9 + 7.
5. Modular arithmetic in Solving Linear Congruence:
Modular arithmetic can be used to solve linear congruence, which are equations of the form ax ≡ b (mod m). These types of problems often appear in number theory and cryptography.
Contact Us