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): https://codeforces.com/contestInvitation/bfde06ab8c7726cc3f6f52c111d6ca83e4a7dfe4
Problem difficulties (and sources): https://pastebin.com/Tt26QKbM
Stream time (actually 1.5 days since upload, not 2.5 days): https://www.timeanddate.com/worldclock/fixedtime.html?msg=Topic+Stream+9&iso=20211012T0935&p1=263
https://docs.google.com/presentation/d/1W-9cgYKU5tmIWC_KViemBunD1EB2ltXKDbo7EFkMun0/edit?usp=sharing (slides)
https://cp-algorithms.com/algebra/phi-function.html (totient function)
https://discuss.codechef.com/t/guide-to-modular-arithmetic-plus-tricks-codechef-edition-there-is-no-other-edition/67424 (proof of Fermat’s little theorem, and some more stuff on modulo)
https://cp-algorithms.com/algebra/factorization.html (some more prime factorization methods)
https://github.com/maksim1744/programming-library/blob/master/factorizer.cpp (super fast prime factorization)
https://brilliant.org/wiki/extended-euclidean-algorithm/ (explains the extended GCD algorithm)
https://codeforces.com/blog/entry/53925 (information on the Mobius inversion)
https://codeforces.com/contest/803/problem/F (problem related to Mobius inversion)
[Related to the above problem, my modified version is problem J in the mashup.]
https://discuss.codechef.com/t/more-intuitive-explanation-for-the-harmonic-seriess-sum/67287 (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 https://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