Number Theory
Euler totient, CRT, prime factorization, and modular arithmetic through 10 problems.
Lessons
1. Introduction to Number Theory
Mathematical foundations for CP
2. Techniques Overview
What you'll learn
3. Codeforces 1295D Same GCDs - Problem Statement
CF 1295D - count values with same GCD
4. Codeforces 1295D Same GCDs - Solution
Reduce to totient calculation
5. Codeforces 1295D Same GCDs - Implementation
Totient via prime factorization
6. Codeforces 1295D Same GCDs - Example and Complexity Analysis
Square root factorization
7. Codeforces 687B Remainders Game - Problem Statement
CF 687B - determine value from remainders
8. Codeforces 687B Remainders Game - Why Naive Fails
Can't enumerate all possible x
9. Codeforces 687B Remainders Game - Solution
Check prime power coverage
10. Codeforces 687B Remainders Game - Implementation
Check prime power divisibility
11. Codeforces 687B Remainders Game - Example and Complexity Analysis
Factorization plus linear scan
12. Codeforces 1033D Divisors - Problem Statement
CF 1033D - factor product of semiprimes
13. Codeforces 1033D Divisors - Why Naive Fails
Numbers are too large to factor directly
14. Codeforces 1033D Divisors - Solution
GCD to find shared primes
15. Codeforces 1033D Divisors - Implementation
GCD-based factorization
16. Codeforces 1033D Divisors - Example and Complexity Analysis
Quadratic in input size
17. Codeforces 1748D ConstructOR - Problem Statement
CF 1748D - find x with OR divisibility
18. Codeforces 1748D ConstructOR - Solution
Use LCM for bit construction
19. Codeforces 1748D ConstructOR - Implementation
Construct x from LCM
20. Codeforces 1748D ConstructOR - Example and Complexity Analysis
Constant time construction
21. Codeforces 1761D Carry Bit - Problem Statement
CF 1761D - count pairs with k carries
22. Codeforces 1761D Carry Bit - Why Naive Fails
Exponential pair count
23. Carry Bit - Key Insight
Carry sequence structure
24. Codeforces 1761D Carry Bit - Solution
Count carry sequences
25. Codeforces 1761D Carry Bit - Implementation
Direct formula with combinatorics
26. Codeforces 1761D Carry Bit - Example and Complexity Analysis
Linear precomputation
27. Codeforces 1244C The Football Season - Problem Statement
CF 1244C - find win/draw/loss counts
28. Codeforces 1244C The Football Season - Solution
Small iteration on draws
29. Codeforces 1244C The Football Season - Implementation
Iterate draws up to w
30. Codeforces 1244C The Football Season - Example and Complexity Analysis
Linear in point values
31. Codeforces 1493D GCD of an Array - Problem Statement
CF 1493D - dynamic GCD with updates
32. Codeforces 1493D GCD of an Array - Why Naive Fails
Recomputing GCD is too slow
33. Codeforces 1493D GCD of an Array - Solution
Track min exponent per prime
34. Codeforces 1493D GCD of an Array - Implementation
Multiset per prime
35. Codeforces 1493D GCD of an Array - Example and Complexity Analysis
Per-prime multiset operations
36. Codeforces 1884D Counting Rhyme - Problem Statement
CF 1884D - count coprime pairs not dividing any element
37. Codeforces 1884D Counting Rhyme - Why Naive Fails
Quadratic pair counting
38. Counting Rhyme - Key Insight
Exact GCD via inclusion-exclusion
39. Codeforces 1884D Counting Rhyme - Solution
Iterate by GCD value with validity check
40. Codeforces 1884D Counting Rhyme - Implementation
Count by GCD with exclusion
41. Codeforces 1884D Counting Rhyme - Example and Complexity Analysis
Harmonic sum complexity
42. Quiz: Number Theory
Test your understanding
43. Section Recap
What you've learned