### obito022's blog

By obito022, history, 19 months ago,

I am trying to learn math for competitive programming. I want to start with Number Theory and I am confused. I don't know how to start with it and and actually use it to solve cp problems. I can easily solve implementation, string etc. problems but when I see some math numbers, symbols I get scared. so how I can I acquire the knowledge about math in general for cp? someone please help me out! And I am still in high school and I don't have that much experience with extreme math. I have never been to any math competition.

• +6

| Write comment?
 » 19 months ago, # |   +4 You need to get comfortable with these topics primarily Divisibility Congruence, residue classes Primes, properties of primes, prime power factorization gcd, properties of gcd, lcm euclid's algorithm for gcd, and extended euclid for linear diophantine equations chinese remainder theorem Number Systems in different bases, and related properties Here are some algorithms you would definitely need to know - Bigmod (fast exponentiation under modulo) - Inverse mod (conditions for existence) - Sieve for precalculation of primes - Factorization, prime-power factorizationFor the theoretical topics, you should check out some books, I recommend 104 Number Theory Problems from USA IMO Training, you can also try to find your way through these Michael Penn — Number TheoryBut after having some basic knowledge, it's just solving a lot of problems, mastery comes with practice. Some of the more intermediate topics include totient function Number of Divisors Sum of Divisors General properties of multiplicative functions Wilson's Theorem Miller Rabin primality detection Pollard Rho factorization
•  » » 19 months ago, # ^ |   +1 Thanks Bhai!
•  » » 2 weeks ago, # ^ |   0 that's the point __
 » 19 months ago, # |   0 Hi!You can learn the math for CP on USACO Guide. We are still developing our modules, so we don't have every possible math topic that will come up in a CP contest; however, USACO Guide is definitely a great introduction to the math required for CP.Here are the modules I recommend you look at: You can also gain math experience by solving problems with the math tag, and use the editorials for help on specific problems. There are also plenty of good CF blogs out there, so I recommend you use that.
•  » » 19 months ago, # ^ |   +3 Hi, how about adding the subset of lectures from this playlist on NT by Richard E. Borcherds to Divisibility and Modular Arithmetic Resources. I like them. Please have a look, when you find time. obito022, you can also follow it. Doing upto lecture no. 17 and solving problems will suffice the requirement for now imo.
 » 19 months ago, # |   0 watch utkarsh guptas math in cp series in unacademy it is free and one of the best.
 » 19 months ago, # | ← Rev. 2 →   +1 Thanks everyone! I didn't expect these many response. I hope all of you will help me in my future journey! Thanks again!
 » 9 months ago, # |   0 What should I study in number theory for problems between (1000-1600) ? because I don't want to learn things that I don't use at my current level
 » 4 weeks ago, # |   0 help me pls!!!!