Applications of Number Theory in Competitive Coding: Part 2

This document explores further applications of number theory in competitive coding, focusing on modular arithmetic and modular inverse, with Java examples.

Modular Arithmetic

Modular arithmetic deals with remainders after division. The expression a mod m (written as a % m in many programming languages, including Java) gives the remainder when a is divided by m. Key properties make it powerful in competitive programming:

• (a + b) mod m = (a mod m + b mod m) mod m
• (a * b) mod m = (a mod m * b mod m) mod m
• (a - b) mod m = (a mod m - b mod m + m) mod m (Adding m avoids negative remainders)

These properties allow performing large calculations efficiently modulo a chosen number, preventing integer overflow and often significantly simplifying problems.

Why Use Modular Arithmetic in Competitive Coding?

• Preventing Overflow: Many problems involve calculating very large numbers. Using modular arithmetic keeps the results within manageable bounds.
• Simplifying Calculations: Modular arithmetic often reduces complex calculations to simpler ones.
• Specific Problem Requirements: Some problems directly ask for the result modulo a given number.

Java Examples of Modular Arithmetic

 public class ModularArithmetic {

            public static long addModulo(long a, long b, long m) {
                return (a % m + b % m) % m;
            }

            public static long multiplyModulo(long a, long b, long m) {
                return (a % m * b % m) % m;
            }

            public static long subtractModulo(long a, long b, long m) {
                return ((a % m - b % m) + m) % m; // Add m to avoid negative remainders
            }

            public static void main(String[] args) {
                long a = 1000000000;
                long b = 2000000000;
                long m = 1000000007;

                System.out.println("Sum modulo " + m + ": " + addModulo(a, b, m));
                System.out.println("Product modulo " + m + ": " + multiplyModulo(a, b, m));
                System.out.println("Difference modulo " + m + ": " + subtractModulo(b, a, m));
            }
        } 

Modular Inverse

The modular inverse of an integer a modulo m is an integer x such that (a * x) mod m = 1. It exists if and only if a and m are coprime (i.e., their greatest common divisor (GCD) is 1). The modular inverse is essential for performing division in modular arithmetic.

Methods to Calculate Modular Inverse

1. Extended Euclidean Algorithm: This is a common and efficient method. It finds integers x and y such that ax + my = gcd(a, m). If gcd(a, m) = 1, then x is the modular inverse of a modulo m.
2. Fermat's Little Theorem: If m is a prime number, then a^(m-1) mod m = 1. Therefore, the modular inverse of a modulo m is a^(m-2) mod m. This works *only* if `m` is prime.
3. Binary Exponentiation: Efficient way to compute a^n mod m, crucial for Fermat's Little Theorem approach.

Java Examples of Modular Inverse

1. Extended Euclidean Algorithm

 public class ModularInverse {

            // Extended Euclidean Algorithm to find GCD(a, b) and coefficients x, y such that ax + by = GCD(a, b)
            public static long[] extendedGCD(long a, long b) {
                if (b == 0) {
                    return new long[] {a, 1, 0}; // GCD, x, y
                }

                long[] result = extendedGCD(b, a % b);
                long gcd = result[0];
                long x1 = result[1];
                long y1 = result[2];

                long x = y1;
                long y = x1 - (a / b) * y1;

                return new long[] {gcd, x, y};
            }


            public static long modularInverse(long a, long m) {
                long[] result = extendedGCD(a, m);
                long gcd = result[0];
                long x = result[1];

                if (gcd != 1) {
                    // Inverse doesn't exist
                    return -1;
                }

                // Ensure x is positive
                return (x % m + m) % m;
            }


            public static void main(String[] args) {
                long a = 3;
                long m = 11;
                long inverse = modularInverse(a, m);

                if (inverse != -1) {
                    System.out.println("Modular inverse of " + a + " modulo " + m + " is: " + inverse);
                    System.out.println((a * inverse) % m); //should output 1
                } else {
                    System.out.println("Modular inverse doesn't exist.");
                }
            }
        } 

2. Fermat's Little Theorem (with Binary Exponentiation)

 public class ModularInverseFermat {

            // Binary exponentiation to calculate a^b mod m
            public static long power(long base, long exp, long m) {
                long res = 1;
                base = base % m;

                while (exp > 0) {
                    if (exp % 2 == 1)
                        res = (res * base) % m;

                    base = (base * base) % m;
                    exp /= 2;
                }
                return res;
            }

            public static long modularInverse(long a, long m) {
                // Only works if m is prime
                return power(a, m - 2, m);
            }

            public static void main(String[] args) {
                long a = 3;
                long m = 11;  // m *must* be prime for Fermat's Little Theorem to work.
                long inverse = modularInverse(a, m);

                System.out.println("Modular inverse of " + a + " modulo " + m + " is: " + inverse);
                System.out.println((a * inverse) % m); //should output 1
            }
        } 

Example Competitive Coding Problem

Problem: Given an array of integers nums and an integer k, find the number of subarrays whose product is divisible by k, modulo 10^9 + 7.

Conceptual Approach: Calculating the product of even relatively small `nums` values might lead to overflow issues and slow down the program. In order to overcome this, we should divide the elements of the array by the greatest common divisor (GCD) between `k` and the element in the array.
Then we need to calculate the inverse of the the `GCD` in modulo format using previously written code.
After dividing by the GCD, the products will no longer lead to overflow and the problem is solved.

Note: This is a simplified example. The actual implementation will depend on the specific constraints and the size of the input.