Appendix G ~50 min read Intermediate

Appendix G: Mathematical Algorithm Fundamentals

English translation of this chapter is coming soon. Please refer to the Chinese version for now.

Content Outline

G.1 Prime Sieve Methods

  • Why Do We Need Sieve Methods?
  • G.1.1 Sieve of Eratosthenes
  • G.1.2 Euler's Linear Sieve (Optimal Sieve)
  • G.1.3 Sieve Method Comparison

G.2 Fast Exponentiation

  • Binary Decomposition of the Exponent
  • Complete Implementation
  • Modular Inverse (Fermat's Little Theorem)
  • Computing Combinations C(n, k) mod p

G.3 Interval Dynamic Programming (Interval DP)

  • What is Interval DP?
  • State Transition Framework
  • Traversal Order: By Interval Length
  • G.3.1 Classic Example: Stone Merging
  • G.3.2 Variant: Bracket Matching

G.4 Matrix Fast Exponentiation (Accelerating Linear Recurrences)

  • Applicable Scenarios
  • Fibonacci Sequence Example

Common Mistakes

Exercises

  1. Prime Factorization
  2. Combinations mod p
  3. Stone Merging (Interval DP Basics)
  4. Matrix Chain Multiplication (Classic Interval DP)
  5. N-th Fibonacci Number (Matrix Fast Exponentiation)
  6. Cow Trading (Interval DP Variant)
  7. Sum of All Primes Below 1000
  8. String Encryption (Fast Exponentiation Application)