Number Theory for Competitive Programming | Topic Stream 9
Ғылым және технология
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
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.
Hey Colin, thanks for putting this video, really appreciate.
Thanks Colin, your lecture videos are very helpful for learning competitive programming, really appreciate.
Thank you so much for this video, i was actually looking for a good source on Number theory and i find this. ❤
Thanks for all the amazing videos, Im learning a lot!
This one helps a lot. Not enough concise breakdowns of this topic out there
Thanks for all the amazing Videos. Big fan of you .
Looking forward to it!
Long waiting but worth it❤️❤️
Thanks, you're really awesome!
thanks, colin...love from Bangladesh
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 ?
Thanks alot for a lecture!
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
Thanks dude ❣️
thanks colin .
Thank you so much
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....
in more modulo: any one can tell me why we need to do b^c%totient(m)? ! any links to this ?
Thank you 👍
thank u so much
How do you do division for mod in number theory? It seems to work only for + and *
@AmanSharma-or5vh
Жыл бұрын
multiplicative modular inverse
hey colin, much love from north korea
Thanks
32:20 it's Möbin time!!
The pastebin link isn't working !
7:05 what is that?
Colin I m coming
thanks
❤