Primes

If you not have already known, primes are numbers that have only 2 unique factors (1 and itself). All negative numbers, 0 and 1 are not considered primes.

Trial Division

Given a number X, tell me whether its a prime or not.

One way this could be solved is using trial division up to (and including) the square root of the number. This method yields a complexity of O(sqrt(X)) per check.

Miller Rabin

When you are asked to check whether X is a prime, and X is very large, trial division will take a long time.

There is an alternative method called miller rabin which will enable you to check for primes very fast, but compromising on accuracy.

Adjust the value of K to vary the run time and accuracy.

Sieve of Eratosthenes

Sieve of Eratosthenes is a quick way of generating primes up to a number N. The time complexity is about O(N log N).

It starts off by assuming every integer above 1 are primes. For each prime found, it will set multiples of the prime to be non-prime.

Is there anyway to speed up the above code if the list of primes is not required?

Prime Factorization

To effectively factorize numbers, you will need a sorted list of primes up to the square root of that number.

For a number X, the algorithm runs in a time proportional to the number of primes below its square root. (excluding generation of the prime list).

Greatest Common Divisor

The greatest common divisor (GCD) of two numbers is the largest integer that can divide the two numbers without any remaider.

Euclidean Algorithm

We can calculate the GCD of two numbers efficiently using Euclidean Algorithm. This algorithm runs in O(log₁₀(X)) where X is the larger of the two numbers. The proof for this algorithm is quite long and it is recommended that you just memorize the following function:

Common Prime Factors

Another way to calculate GCD is to first calculate the prime factors of the two numbers. By multiplying the prime factors in common, the GCD of the both numbers will be obtained.

The utilization of the below function is bounded by the time complexity of the prime factorization. This is slower than the euclidean algorithm but this might be the only way to calcualte GCD for larger numbers that do not fit into the range of long long.

The below code computes the GCD of the two numbers (up to 1million) repeatly, utilizing the above library codes.

Lowest Common Multiple

To calculate the lowest common multple (lcm) between two numbers, we can utilize the greatest common divisor of the two numbers. To be more precise lcm(a, b) = a*b/gcd(a, b)

Modular Arithmetic

Problem setters usually ask for you to print the "answer mod M" when the answer overflows the limits of int/long long. Hence, it is important to know how to utilize such restrictions and compute your answer.

Basic Modular Arithmetic Operations

We can add, multiply and subtract remainders normally as the following equations are true.

Hence, for questions asking for "answer mod M", it is sufficient to just calculate the "intermediate answer mod M" for your intermediate steps to avoid overflow.

Subtraction requires an additional + M before doing the final mod as (B % M) might be larger than (A % M), which will yield a negative number when mod M. Hence, to keep the result positive, we need to add M to the subtraction of (A % M) by (B % M).

Modular Division

However, it is not possible to just divide (A % M) by (B % M) and expect to obtain (A/B) % M. Instead, if B is sufficiently small, we can calculate (A % BM) in all our intermediate steps and then output (A % BM)/B instead.

Another method would be to try to cancel the greatest common divisor of both A and B before trying to do modular arithmetic. This is possible if A and B can be converted to a list of prime factors instead of dealing with the raw numerical integer value.

Code for this section is omitted as it is rarely the intention of the problem setter to make contestants fret over modular division instead of the real problem. Perhaps there might be another way to approach the question without modular division.

Quick Exponentiation

Quick Exponentiation is the technique of using divide and conquer to raise the power of something quickly. In general, to raise something to a power of X, the complexity of the operation is O(log X), which is significantly faster than naive multiplication which will take O(X). The basic idea of quick exponentiation is that squaring a power requires O(1). For example, one can compute 13⁸ by squaring 13 a total of 3 times. (Eg: 13⁸ = ((13²)²)^{2 )}

Integer Exponentiation

When asked to compute A^B mod M and M fits into the range of a 32-bit signed integer, the following code can be used.

Long Long Exponentiation

However, when asked to compute A^B mod M and M fits into the range of a 64-bit signed integer, the above code cannot be used.

Instead, if M*2 still fits within the range of a 64-bit signed integer (Eg: M ≤ 10¹⁸), quick exponentiation is still possible without big integer.

To do so, we will compute X * Y mod M using divide and conquer as well, using 'qmult'.

Matrix Exponentiation

Quick exponentiation can also be applied to matrix as well. The Xth fibonacci can be computed quickly by exponentiating the 2x2 matrix: { {1, 1}, {1, 0} }. This matrix also co-incidentally represents { {Fib 2, Fib 1}, {Fib 1, Fib 0} } and multiplying { {Fib 2, Fib 1}, {Fib 1, Fib 0} } with { {1, 1}, {1, 0} } it results in { {Fib 3, Fib 2}, {Fib 2, Fib 1} }.

In general { {1, 1}, {1, 0} } ^X will result in { {Fib X+1, Fib X}, {Fib X, Fib X-1} }

The following code illustrates the fibonacci matrix exponentiation and is an accepted solution for mrJudge problem, fibo_ex