数学 1

HYYW1228 · 2023-12-29 22:02:43 · 个人记录

Miscellaneous

• Equations

  • Notice the constraints

    • Sometimes, there is a very big input range,and maybe there are some operations. If binary search would not work, try to find if a cycle exists, or breakpoints (upper bound) of checking. Cycles exist not only in graph related problems :D

  • Try to write out some inequalities

  • When you are given an equation, try to move terms so you get a friendly expression. This helps you to make the problem easier.

  • When you are not given an equation, still try to write out some equations according to the constraints given.

  • Think backwards (Simplification of inclusion and exclusion principle)

• De Morgan's laws: Used in logical operations

• Binet's Formula: Calculates the i-th term of fibonacci sequence.

• \sum_{i=1}^{k} i^2 = \frac{k(k+1)(2k+1)}{6}
• \sum_{i=1}^{k} i^3 = (\frac{k(k+1)}{2})^2
  • Even exists a general formula, but too long

• Arithmetic and Geometric sequences Formula (There are also some other forms of the formulas but they are fundamentally same)

  • \frac{n(a+b)}{2}
  • \frac{bk-a}{k-1}
  • QM \geq AM \geq GM \geq HM

• Calculating GCD by using Euclidean Algorithm.

• Calulating exponent by using binary jumping.

• \frac{1}{n}\sum_1^n a_i \geq \sqrt[n]{\prod_1^n} a_i
  • Arithmetic mean only equal to geometric mean when all terms are equal: a_i = a_{i+1}, \forall 1 \leq i < n

• Vieta's Theorem: \sum_1^nr_i = - \frac{c_{n-1}}{c_n}, \prod_1^n r_i = (-1)^n \frac{c_0}{c_n}

  Bezout’s identity :

  ax + by = c$ exists an integer solution for $x, y$ iff $gcd(a, b) | c

推论: a_1x_1 + a_2x_2 + \dots + a_nx_n = c iff gcd(a_1, a_2, \dots, a_n) | c

- Pell's Equation (?这是什么)

Example problems:

Watering an Array

好数

Ela's Fitness and the Luxury Number

Torn Lucky Ticket

USACO Bakery S

Matching Numbers

Martial Arts Tournament

Combinatorics

• Fermat's Little Theorem: x^{p-1} \equiv 1 \space \mod p, where x and p are coprime.

  • So \frac{x}{y} \equiv x \times y^{p-1} \mod p

  • Inclusion and exclusion principle

  • When something is hard to get, try to get this by using inclusion exclusion principle. The logic applies in other aspects as well, think backwards.

  • Pascal's Identity: {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}

Example problems:

Remove 2 Letters

RELATIVNOST

Selling Paint (Derived problem from RELATIVNOST)

Graduation Trip

Number Theory and Modular Arithmetics

GCD and LCM

int gcd(int a, int b) {return !b? a: gcd(b, a%b);}

定义

常见性质

1. 对于任意整数m, (ma_1, ma_2, ..., ma_n) = m \times (a_1, a_2, ..., a_n)

   • 该性质同样适用于LCM

2. 对于任意整数x, y: (a, b) = (a+bx, b) = (a, b+ay)

   • 不适用于LCM

3. 结合律(a_1, a_2, ... a_{k+r}) = ((a_1, a_2, ..., a_k), (a_{k+1}, a_{k+2}, ..., a_{k+r}))

   • 该性质同样适用于LCM
4. pq = (p, q) \times [p, q]

5. 不算严格的数学性质？因为这里的\gcd默认是根据c++的实现定义的，也就是说如果某个参数为0, 他不会被考虑

   • \gcd(a_1, a_2, ..., a_n) = \gcd(a_2-a_1, a_3-a_2, a_4-a_3, ..., a_n-a_1, a_k)
   • 1 \leq k \leq n

   • 证明很简单:

     • lhs \geq rhs

     • 设g = \gcd(a_i)

     • g | a_{i+1} - a_i \forall \space 1\leq i < n, g|a_k

     • 所以g也是rhs的最大公约数。

       算数基本定理

• a = p_1^{a_1} p_2^{a_2} p_3^{a_3} ... p_n^{a_n}
  • 一个大于1的数字可以被表示为若干质数的积且两两不 相同

• 推论1

  • \forall 1 \leq i \leq n, e_i \leq a_i

• 推论2

  • x$和$y$可以为$0
  • (a, b) = \prod p^{\min(a_x, a_y)}
  • [a, b] = \prod p^{\max(a_x, a_y)}

• 推论3

  • a$的约数个数$\sigma(a) = (a_1+1)(a_2+1)...(a_n+1)

  • 每一个质因数的最高次幂+1的乘机

• 推论4

  • a$的约数之和$\tau(a) = \prod_{i=1} \sum_{j=0}^{a_i} p^j = (1 + p_1^1 +... + p_1^{a_1})(1+p_2^1 + ... + p_2^{a_2}) ... (1 + p_n^1 + ... + p_n^{a_n})

Modular Arithmetics

• Remainders repeat after a cycle. You might think this is something obvoius, but it is something that is very easy to overlook.

• When a \equiv r \mod k and k is doubled. The remainder either stays the same, or a \equiv r + k \mod 2k.

  • Generalize it: a \equiv r \mod k: \exists 0 \leq j < n, s.t. \space a \equiv r + jk \mod nk.

Fermat's Little Theorem

Example problems

题单1

USACO Loan Repayment S