Number Theory for Competitive Programming

Number Theory for Competitive Programming | Topic Stream 9

Рет қаралды 43,461

Күн бұрын

Tutorial on number theory, including most of the basic stuff and a few more advanced things. Note the rather unusual stream time. Sorry that this has (repeatedly) been delayed - for whatever reason, I had a huge aversion to actually recording this, and I'm not sure why.
Links:
Mashup (practice problems): codeforces.com/contestInvitat...
Problem difficulties (and sources): pastebin.com/Tt26QKbM
Stream time (actually 1.5 days since upload, not 2.5 days): www.timeanddate.com/worldcloc...
docs.google.com/presentation/... (slides)
cp-algorithms.com/algebra/phi... (totient function)
discuss.codechef.com/t/guide-... (proof of Fermat’s little theorem, and some more stuff on modulo)
cp-algorithms.com/algebra/fac... (some more prime factorization methods)
github.com/maksim1744/program... (super fast prime factorization)
brilliant.org/wiki/extended-e... (explains the extended GCD algorithm)
codeforces.com/blog/entry/53925 (information on the Mobius inversion)
codeforces.com/contest/803/pr... (problem related to Mobius inversion)
[Related to the above problem, my modified version is problem J in the mashup.]
discuss.codechef.com/t/more-i... (why sum of i from 1 to n of n/i is O(n * log n))
AnandOza has also done a similar stream (I’m just doing this because it was voted on), see codeforces.com/blog/entry/85475
Timestamps:
Intro + tip 00:00
Floor/ceil 01:30
Divisors 01:58
Prime factorization 03:40
Divisor finding 05:43
Modulo 07:00
Binary exponentiation 10:54
Modular "division" 13:11
GCD 17:21
Extended Euclidean (kinda) 21:06
LCM 23:21
Chinese remainder theorem 24:30
Instance of mobius 32:12
Conclusion 36:45

Пікірлер: 33

@Selbstzensur Жыл бұрын

I love all the content creator out there. I pick the ones who help me to get rid of my flaws, who help me to grow and this is so awesome. Thank you for beeing one of these creators.

@harrisondong5405 Жыл бұрын

Thanks Colin, your lecture videos are very helpful for learning competitive programming, really appreciate.

@aries3690 2 жыл бұрын

Thanks for all the amazing videos, Im learning a lot!

@gdthegreat 2 жыл бұрын

Hey Colin, thanks for putting this video, really appreciate.

@user-to8uo3ir2r 10 ай бұрын

Thanks for all the amazing Videos. Big fan of you .

@MyPlanetIsPluto 2 жыл бұрын

This one helps a lot. Not enough concise breakdowns of this topic out there

@shivanshsahu3781 2 жыл бұрын

Thank you so much for this video, i was actually looking for a good source on Number theory and i find this. ❤

@AlgorithmsConquered 2 жыл бұрын

Looking forward to it!

@jaidmmx_3290 2 жыл бұрын

Thanks, you're really awesome!

@salambience12 2 жыл бұрын

thanks, colin...love from Bangladesh

@sammkk8700 2 жыл бұрын

Long waiting but worth it❤️❤️

@shanewalsch 2 жыл бұрын

Thanks alot for a lecture!

@MiketheCoder 2 жыл бұрын

How do you do division for mod in number theory? It seems to work only for + and *

@AmanSharma-or5vh Жыл бұрын

multiplicative modular inverse

@user-fb7hw1el1c 2 жыл бұрын

Thank you so much

@Aditya-cw7rd 2 жыл бұрын

Thanks dude ❣️

@LinuxKernel-lf8ov 5 ай бұрын

Hello, i have a question when you say "lets subtract a from both sides" in the equation (cx+a)%y = b the equation become (cx+a)%y - a = b-a so what are the math steps to simplify it to be cx%y = (b-a)%y and second question is how the %y got to be a part for the right hand side ?

@coefficient1359 2 жыл бұрын

Thank you 👍

@nirajandata 2 жыл бұрын

thanks colin .

@kxb6098 2 жыл бұрын

Please correct me if I'm wrong: gcd(a, b) = gcd(a - b, b) gcd(a, b) = gcd(a + b, b) right?

@maxbro8880 2 жыл бұрын

yes, that is how Euclid's algo works gcd(a, b) = gcd(a + kb, b) for any integer k

@VIVEKMMMUT-ECE2027 2 ай бұрын

more efficent would be a%b,b since a-b is same as a%b if done multiple times

@solaris413 2 жыл бұрын

thank u so much

@hloboy8811 2 жыл бұрын

Thanks

@shivamkushwah3542 2 жыл бұрын

hey galen....i dont think if this is a popular opinion.....but i like your freestyle teaching more than making slides like this.......when we see someone writing or typing it keeps us engaged.......although the content is still awesome....your freestyle teaching is the thing that makes you different and better than others and obviously the content too....