Mathematics For Competitive Programming

Hello guys,

I am writing about most of the mathematics topics involved in competitive Programming.

GCD (Greatest Common Divisor)
Properties of GCD
Brute Force and Euclidean algorithm to compute GCD
Analysis of Euclidean algorithm

Modular Arithmetic
Basic properties of modulo
proof of condition for inverse modulo to exist
Modulo inverse using extended euclidean algorithm with proof
Modulo inverse using Fermat’s theorem
Solution of Modulo inverse of all integers less than m

Prime Numbers
Properties of prime
Wilson’s theorem
School method for primality testing
Fermat’s theorem and its drawbacks
Miller-Rabin test with proof
Why Miller-Rabin is better
Deterministic version of Miller-Rabin
Seive of Eratosthenes

Prime Factors
Properties of Prime Factors
Proof of Number of divisors
Trial Division Method for Prime Factors
Optimization for trial Division method
O(N^{1/3}) algorithm for calculating number of divisors
Logarithmic Prime Factorisation Using Seive

Combinatorics (coming soon)

Probability (coming soon)

Geometry (coming soon)

Miscellaneous topics (coming soon)

Please tell me if something is wrong or you would like me to add some more information.

Thank you and Happy Coding


in part 1- you have included only the most general part there is a more in that topic like gcd in an interval and relations btw gcd and lcm.

1 Like

Thanks for the suggestion! I thought relation between gcd and lcm was trivial and I didn’t thought of gcd in an interval. I will add both of them very soon

1 Like

good boi XDXD

1 Like