In the world of competitive programming, understanding number theory and modular arithmetic is crucial. These concepts help in solving a wide range of problems efficiently. In this article, we will explore the basics of modular arithmetic and delve into some popular number theory algorithms used in competitive programming, using Java as our chosen programming language.

Modular arithmetic involves performing arithmetic operations on remainders. It is based on the concept that if two numbers have the same remainder when divided by a positive integer, then the result of any arithmetic performed on these numbers will be the same modulo that positive integer.

In modular addition, we add two numbers and take the result modulo a positive integer. It can be defined as:

`(a + b) % M = (a % M + b % M) % M`

Similar to modular addition, modular subtraction can be defined as:

`(a - b) % M = (a % M - b % M + M) % M`

Modular multiplication follows the same rules as regular multiplication, with the additional step of taking the modulo for each intermediate calculation. It can be defined as:

`(a * b) % M = (a % M * b % M) % M`

Modular exponentiation is used when we need to calculate large powers modulo a positive integer. It can be defined using the concept of **exponentiation by squaring**:

```
(a^b) % M = (a^(b/2) % M * a^(b/2) % M) % M if b is even
(a^b) % M = (a * a^(b-1) % M) % M if b is odd
```

Now that we have covered the basics of modular arithmetic, let's explore some popular number theory algorithms that are frequently used in competitive programming.

The GCD of two numbers is the largest positive integer that divides both numbers without leaving a remainder. It can be efficiently calculated using the **Euclidean Algorithm**:

```
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
```

The Sieve of Eratosthenes is an efficient algorithm to find all prime numbers up to a given limit. It is based on the principle that if a number is prime, all its multiples are not. The algorithm works as follows:

```
boolean[] sieve(int n) {
boolean[] isPrime = new boolean[n + 1]; // Initialize a boolean array
Arrays.fill(isPrime, true); // Mark all numbers as prime initially
isPrime[0] = isPrime[1] = false; // 0 and 1 are not prime
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false; // Mark multiples of i as non-prime
}
}
}
return isPrime;
}
```

Prime factorization is the process of finding the prime factors of a given number. It can be efficiently done using **trial division**:

```
List<Integer> primeFactorization(int n) {
List<Integer> factors = new ArrayList<>();
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
factors.add(i);
n /= i;
}
}
if (n > 1)
factors.add(n);
return factors;
}
```

In this article, we explored the concepts of modular arithmetic and several number theory algorithms used in competitive programming. Understanding these concepts not only helps in solving problems efficiently but also forms the foundation for tackling more advanced algorithms in this field. By implementing and practicing these algorithms in Java, you will be better equipped to handle challenging competitive programming problems involving modular arithmetic and number theory.

noob to master © copyleft