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

Star and Bars - Combinatorics(Latest Post)
-> Star and Bars theorem with proof
-> Number of non-negative integer sum
-> Number of lower bound integer sum
-> Coefficient of x^n in (1-x)^{-k}

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

15 Likes

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