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

  • @Selbstzensur
    @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.

  • @gdthegreat
    @gdthegreat2 жыл бұрын

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

  • @harrisondong5405
    @harrisondong5405 Жыл бұрын

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

  • @shivanshsahu3781
    @shivanshsahu37812 жыл бұрын

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

  • @aries3690
    @aries36902 жыл бұрын

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

  • @MyPlanetIsPluto
    @MyPlanetIsPluto2 жыл бұрын

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

  • @user-to8uo3ir2r
    @user-to8uo3ir2r10 ай бұрын

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

  • @AlgorithmsConquered
    @AlgorithmsConquered2 жыл бұрын

    Looking forward to it!

  • @sammkk8700
    @sammkk87002 жыл бұрын

    Long waiting but worth it❤️❤️

  • @jaidmmx_3290
    @jaidmmx_32902 жыл бұрын

    Thanks, you're really awesome!

  • @salambience12
    @salambience122 жыл бұрын

    thanks, colin...love from Bangladesh

  • @LinuxKernel-lf8ov
    @LinuxKernel-lf8ov5 ай бұрын

    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 ?

  • @shanewalsch
    @shanewalsch2 жыл бұрын

    Thanks alot for a lecture!

  • @kxb6098
    @kxb60982 жыл бұрын

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

  • @maxbro8880

    @maxbro8880

    2 жыл бұрын

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

  • @VIVEKMMMUT-ECE2027

    @VIVEKMMMUT-ECE2027

    2 ай бұрын

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

  • @Aditya-cw7rd
    @Aditya-cw7rd2 жыл бұрын

    Thanks dude ❣️

  • @nirajandata
    @nirajandata2 жыл бұрын

    thanks colin .

  • @user-fb7hw1el1c
    @user-fb7hw1el1c2 жыл бұрын

    Thank you so much

  • @shivamkushwah3542
    @shivamkushwah35422 жыл бұрын

    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....

  • @ziedbrahmi4812
    @ziedbrahmi4812 Жыл бұрын

    in more modulo: any one can tell me why we need to do b^c%totient(m)? ! any links to this ?

  • @coefficient1359
    @coefficient13592 жыл бұрын

    Thank you 👍

  • @solaris413
    @solaris4132 жыл бұрын

    thank u so much

  • @MiketheCoder
    @MiketheCoder2 жыл бұрын

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

  • @AmanSharma-or5vh

    @AmanSharma-or5vh

    Жыл бұрын

    multiplicative modular inverse

  • @wrathcyber
    @wrathcyber2 жыл бұрын

    hey colin, much love from north korea

  • @hloboy8811
    @hloboy88112 жыл бұрын

    Thanks

  • @tanvirhasan4912
    @tanvirhasan49122 жыл бұрын

    32:20 it's Möbin time!!

  • @mohimenul1570
    @mohimenul1570 Жыл бұрын

    The pastebin link isn't working !

  • @mahmoudbassem1434
    @mahmoudbassem1434 Жыл бұрын

    7:05 what is that?

  • @gabbar1867
    @gabbar18672 жыл бұрын

    Colin I m coming

  • @powerofpavan7710
    @powerofpavan77104 ай бұрын

    thanks

  • @akshayas349
    @akshayas3492 ай бұрын