4— layout: post title: “Competitive Programming Beginner Topics Part 2” tags: [Writing, competitive programming,Competitive Programming Beginner] usemathjax: true —

Primal proficiency

1. Basic math

2. Primality, Factorization and Sieve of Eratosthenes

Efficient factorization and prime checking is a must know when it comes to competitive programming. This is the place to start for number theory.

Reading material:

• Introduction - CPH Ch 21: Number theory, pg 197 - 198
• Primality and Prime factorization - CPH Ch 21, pg 199
• Sieve of Eratosthenes
  • CPH Ch 21, pg 200
  • YouTube [V]
  • Visualization [B]
• Prime factorization queries - Tutorial [B]
• Prime gap - Article [B]

3. Euclidean GCD and Euler’s Totient function

You’ll see a fair number of easy mathy problems whose solutions involve finding and using the Greatest Common Divisor (GCD) of some numbers. The Euler totient function is rarer, but it is still good to know.

Reading material:

• Euclid’s algorithm
  • CPH Ch 21, pg 200
  • CP Algorithms
• Euler’s totient function
  • CPH Ch 21, pg 201
  • CP Algorithms
• Topcoder article - click

Tip: Use std::gcd or __gcd() (a builtin function of the GCC compiler).

4. Modular Arithmetic

Have you ever seen something like find the answer modulo 10⁹+7? If you’re still wondering what it means (or even if you’re not), you should read up on Modular arithmetic.

Reading material:

• CF Blog [B]
• Errichto video [V]
• SecondThread video [V]
• Modular Inverse - CP Algorithms
• CPH Ch 21, pg 201 - 203

Try this problem.

My solution in C++

Modint template solution in C++

See snippet for implementation.

4. Binary Exponentiation

Binary exponentiation (also known as exponentiation by squaring) is a trick which allows you to calculate $a^n$ using only $\mathcal{O}(logn)$ multiplications (instead of $\mathcal{O}(n)$ multiplications).

Of course, this also works under mod. This is sometimes referred to as Modular Exponentiation.

Reading material:

• Errichto [V]
• CP Algorithms [B]

Practice

Mashups of topic relevant problems spanning a range of difficulties.

Competitive Programming Beginner Topics Part 3