README.md

Algebra

Greatest Common Divisor

Greatest Common Divisor (GCD) is the largest number which is a divisor of all given numbers. We can compute GCD(a,b) in O(log(min(a,b))).

The two implementations are available. Binary GCD is a little bit more efficient than standard one by using only binary operations.

• GCD | C++ code
• Binary GCD | C++ code

References in English

• Euclidean algorithm for computing the greatest common divisor - Competitive Programming Algorithms

Challenges

• GCD and LCM | CodeChef
• Greatest Common Divisor - AOJ ALDS1B
• Disjoint Set of Common Divisors - AtCoder ABC142D

Least Common Multiple

Least Common Multiple (LCM) is the smallest number which is a multiple of all given numbers. We can also compute LCM(a,b) in O(log(min(a,b))).

• LCM | C++ code

References in English

• Euclidean algorithm for computing the greatest common divisor - Competitive Programming Algorithms

Challenges

• GCD and LCM | CodeChef
• Least Common Multiple - AOJ NTL1C

Binary Exponentiation

Binary exponentiation is a way to calculate the n-th power of a in O(log(n)). The algorithm requires only O(log(n)) multiplications.

Binary Exponentiation | C++ code

References in English

• Binary Exponentiation - Competitive Programming Algorithms

Challenges

• Power - AOJ NTL1B

Prime Factorization

Prime Factorization or Integer Factorization is a way to break a number into a set of prime numbers. All numbers in the set multiply together to result in the original number.

• Trivial | C++ code in O(sqrt(N))

References in English

• Integer Factorization - Competitive Programming Algorithms

Challenges

• Prime Factorization - AOJ NTL1A
• Factorization - AtCoder ABC110D
• Disjoint Set of Common Divisors - AtCoder ABC142D

Binomial Coefficients

Binomial coefficients (n,k) are the number of ways to pick a set of k elements up from n different elements. The order of elements picked up is not taken into account.

• Binomial Coefficients using Pascal's Triangle | C++ code
  • Precomputation in O(N**2)
  • Calculation in O(1)
• Binomial Coefficients in Modulo | C++ code
  • Precomputation in O(N)
  • Calculation in O(1)

References in English

• Binomial Coefficients - Competitive Programming Algorithms

References in Japanese

• 競プロでよく使う二項係数(nCk)を素数(p)で割った余りの計算と逆元のまとめ | アルゴリズムロジック

Combination with repetition

Number of combinations with repetition | Combination - Wikipedia

$$((n, k)) = (n + k - 1, k)$$ $$H(n,k) = C(n+k-1,k)$$

Challenges

• 多重ループ - AtCoder ABC021D
• 経路 - AtCoder ABC034C
• いろはちゃんとマス目 - AtCoder ABC042D
• Maximum Average Sets - AtCoder ABC057D
• Factorization - AtCoder ABC110D
• E - Cell Distance
• D - Bouquet
• E - Roaming
• E - Colorful Blocks

Extended Euclidean Algorithm

Extended Euclidean Algorithm is a way to compute a integer solution (x,y) of ax + by = gcd(a,b). We can compute the solution in O(log(min(a,b))).

• Extended Euclidean Algorithm (iterative solution) | C++ code
• Extended Euclidean Algorithm (recursive solution) | C++ code

References in English

• Extended Euclidean Algorithm - Competitive Programming Algorithms

Challenges

• Extended Euclidean Algorithm - AOJ NTL1E

Modular Multiplcative Inverse

A Modular Multiplicative Inverse of an integer a is an integer x such that the product ax is congruent to 1 in modulus m.

$$ax = 1 (mod m) x = a^{-1} (mod m)$$

• Modular Multiplicative Inverse (using Fermat's little theorem and Binary Exponentation) | C++ code
• Modular Multiplicative Inverse (using Extended Euclidean Algorithm) | C++ code
• All Modular Multiplicative Inverse | C++ code

References in English

• Modular multiplicative inverse - Wikipedia
• Modular Inverse - Competitive Programming Algorithms

Challenges

• D - 動的計画法
• E - Flatten
• E - Throne