返回「邏輯與算法」主頁
本页面仅收录 Useful Formulas & Theorems in CP。对于知识点，另见 邏輯與算法：雜項
恒等式 极值对偶恒等式 x + y = max ( x , y ) + min ( x , y ) ∣ x − y ∣ = max ( x , y ) − min ( x , y ) 2 max ( x , y ) = ( x + y ) + ∣ x − y ∣ 2 min ( x , y ) = ( x + y ) − ∣ x − y ∣ ∣ x − y ∣ = ∣ max ( x , y ) − min ( x , y ) ∣ x + y = ( x ∨ y ) + ( x ∧ y ) x ⊕ y = ( x ∨ y ) − ( x ∧ y ) 2 ( x ∨ y ) = ( x + y ) + ( x ⊕ y ) 2 ( x ∧ y ) = ( x + y ) − ( x ⊕ y ) x ⊕ y = ( x ∨ y ) ⊕ ( x ∧ y ) \begin{aligned} x + y & = \max(x, y) + \min(x, y) \\ |x-y| & = \max(x, y) - \min(x, y) \\ 2 \max(x, y) & = (x + y)+ |x-y| \\ 2 \min(x, y) & = (x + y) - |x-y| \\ \lvert x - y \rvert & = \lvert \max(x, y) - \min(x, y) \rvert \\ \\ x+y & = (x \vee y) + (x \wedge y) \\ x \oplus y & = (x \vee y) - (x \wedge y) \\ 2 (x \vee y) & = (x + y) + (x \oplus y) \\ 2 (x \wedge y) & = (x + y) - (x \oplus y) \\ x \oplus y & = (x \lor y) \oplus (x \land y) \end{aligned} x + y ∣ x − y ∣ 2 max ( x , y ) 2 min ( x , y ) ∣ x − y ∣ x + y x ⊕ y 2 ( x ∨ y ) 2 ( x ∧ y ) x ⊕ y = max ( x , y ) + min ( x , y ) = max ( x , y ) − min ( x , y ) = ( x + y ) + ∣ x − y ∣ = ( x + y ) − ∣ x − y ∣ = ∣ max ( x , y ) − min ( x , y )∣ = ( x ∨ y ) + ( x ∧ y ) = ( x ∨ y ) − ( x ∧ y ) = ( x + y ) + ( x ⊕ y ) = ( x + y ) − ( x ⊕ y ) = ( x ∨ y ) ⊕ ( x ∧ y )
Number Theory p-adic valuation For a prime p p p
If n = p k m n = p^k m n = p k m p ∤ m p \nmid m p ∤ m ν p ( n ) = k \nu_p(n) = k ν p ( n ) = k p p p n n n x ≡ y ( m o d p r ) ⟺ p r ∣ x − y ⟺ ν p ( x − y ) ≥ r x \equiv y \pmod{p^r} \iff p^r \mid x-y \iff \nu_p(x-y) \ge r x ≡ y ( mod p r ) ⟺ p r ∣ x − y ⟺ ν p ( x − y ) ≥ r ν p ( a b ) = ν p ( a ) + ν p ( b ) \nu_p(ab) = \nu_p(a) + \nu_p(b) ν p ( ab ) = ν p ( a ) + ν p ( b ) ν p ( a / b ) = ν p ( a ) − ν p ( b ) \nu_p(a/b) = \nu_p(a) - \nu_p(b) ν p ( a / b ) = ν p ( a ) − ν p ( b ) Let n ∈ N + n \in \mathbb{N}^+ n ∈ N + n = ∏ p ∣ n p ν p ( n ) \displaystyle n = \prod_{p \mid n} p^{\nu_{p}(n)} n = p ∣ n ∏ p ν p ( n )
( a , b ) = gcd ( a , b ) = ∏ p p min ( ν p ( a ) , ν p ( b ) ) (a, b) = \gcd(a, b) = \prod_{p} p^{\min(\nu_{p}(a), \nu_{p}(b))} ( a , b ) = g cd( a , b ) = ∏ p p m i n ( ν p ( a ) , ν p ( b )) [ a , b ] = lcm ( a , b ) = ∏ p p max ( ν p ( a ) , ν p ( b ) ) [a, b] = \operatorname{lcm}(a, b) = \prod_{p} p^{\max(\nu_{p}(a), \nu_{p}(b))} [ a , b ] = lcm ( a , b ) = ∏ p p m a x ( ν p ( a ) , ν p ( b )) a b = ( a , b ) [ a , b ] a b = (a, b)[a, b] ab = ( a , b ) [ a , b ] a ⊥ b ⟺ ( a , b ) = 1 a \perp b \iff (a, b) = 1 a ⊥ b ⟺ ( a , b ) = 1 Lifting The Exponent Lemma (LTE) Let p ≠ 2 p \neq 2 p = 2
p ∣ x − y , p ∤ x ⟹ ν p ( x n − y n ) = ν p ( x − y ) + ν p ( n ) 2 ∤ n , p ∣ x + y , p ∤ x ⟹ ν p ( x n + y n ) = ν p ( x + y ) + ν p ( n ) \begin{aligned} p \mid x - y, \ p \nmid x & \implies \nu_p(x^n-y^n)=\nu_p(x-y) + \nu_{p}(n) \\ 2 \nmid n, \ p \mid x + y, \ p \nmid x & \implies \nu_p(x^n+y^n)=\nu_p(x+y) + \nu_{p}(n) \end{aligned} p ∣ x − y , p ∤ x 2 ∤ n , p ∣ x + y , p ∤ x ⟹ ν p ( x n − y n ) = ν p ( x − y ) + ν p ( n ) ⟹ ν p ( x n + y n ) = ν p ( x + y ) + ν p ( n )
Let p = 2 p = 2 p = 2
2 ∤ n , 2 ∤ x , 2 ∤ y ⟹ ν 2 ( x n − y n ) = ν 2 ( x − y ) 2 ∣ n , 2 ∤ x , 2 ∤ y ⟹ ν 2 ( x n − y n ) = ν 2 ( x − y ) + ν 2 ( x + y ) + ν 2 ( n ) − 1 2 ∤ n , 2 ∤ x , 2 ∤ y ⟹ ν p ( x n + y n ) = ν p ( x + y ) + ν p ( n ) \begin{aligned} 2 \nmid n, \ 2 \nmid x, \ 2 \nmid y & \implies \nu_2(x^n-y^n)=\nu_2(x-y) \\ 2 \mid n, \ 2 \nmid x, \ 2 \nmid y & \implies \nu_2(x^n-y^n)=\nu_2(x-y)+\nu_2(x+y)+\nu_2(n)-1 \\ 2 \nmid n, \ 2 \nmid x, \ 2 \nmid y & \implies \nu_p(x^n+y^n)=\nu_p(x+y) + \nu_{p}(n) \end{aligned} 2 ∤ n , 2 ∤ x , 2 ∤ y 2 ∣ n , 2 ∤ x , 2 ∤ y 2 ∤ n , 2 ∤ x , 2 ∤ y ⟹ ν 2 ( x n − y n ) = ν 2 ( x − y ) ⟹ ν 2 ( x n − y n ) = ν 2 ( x − y ) + ν 2 ( x + y ) + ν 2 ( n ) − 1 ⟹ ν p ( x n + y n ) = ν p ( x + y ) + ν p ( n )
Proof. 设 n = 2 k m n=2^k m n = 2 k m k = ν 2 ( n ) ≥ 1 k = \nu_2(n)\ge1 k = ν 2 ( n ) ≥ 1 m m m A = x 2 k , B = y 2 k A=x^{2^k},B=y^{2^k} A = x 2 k , B = y 2 k A m − B m = ( A − B ) ( A m − 1 + A m − 2 B + ⋯ + B m − 1 ) A^m-B^m=(A-B)(A^{m-1}+A^{m-2}B+\cdots+B^{m-1}) A m − B m = ( A − B ) ( A m − 1 + A m − 2 B + ⋯ + B m − 1 ) m m m ν 2 ( x n − y n ) = ν 2 ( x 2 k − y 2 k ) \nu_2(x^n-y^n)=\nu_2(x^{2^k}-y^{2^k}) ν 2 ( x n − y n ) = ν 2 ( x 2 k − y 2 k ) x 2 k − y 2 k = ( x − y ) ( x + y ) ∏ j = 1 k − 1 ( x 2 j + y 2 j ) x^{2^k}-y^{2^k}=(x-y)(x+y)\prod_{j=1}^{k-1}(x^{2^j}+y^{2^j}) x 2 k − y 2 k = ( x − y ) ( x + y ) ∏ j = 1 k − 1 ( x 2 j + y 2 j ) ν 2 ( x 2 k − y 2 k ) = ν 2 ( x − y ) + ν 2 ( x + y ) + ∑ j = 1 k − 1 ν 2 ( x 2 j + y 2 j ) \nu_2(x^{2^k}-y^{2^k})=\nu_2(x-y) + \nu_2(x+y) + \sum_{j=1}^{k-1}\nu_2(x^{2^j}+y^{2^j}) ν 2 ( x 2 k − y 2 k ) = ν 2 ( x − y ) + ν 2 ( x + y ) + ∑ j = 1 k − 1 ν 2 ( x 2 j + y 2 j ) 8 8 8 1 1 1 j ≥ 1 j\ge1 j ≥ 1 x 2 j + y 2 j ≡ 1 + 1 = 2 ( m o d 8 ) x^{2^j}+y^{2^j}\equiv 1+1=2\pmod8 x 2 j + y 2 j ≡ 1 + 1 = 2 ( mod 8 ) ν 2 ( x 2 j + y 2 j ) = 1 \nu_2 (x^{2^j}+y^{2^j})=1 ν 2 ( x 2 j + y 2 j ) = 1
Legendre Formula (中：勒让德).
ν p ( n ! ) = ∑ k = 1 p k ⩽ n ⌊ n p k ⌋ = n − S p ( n ) p − 1 . \nu_{p}(n!)=\displaystyle\sum\limits_{k=1}^{p^k \leqslant n}\bigg\lfloor\dfrac{n}{p^k}\bigg \rfloor=\dfrac{n-S_p(n)}{p-1}. ν p ( n !) = k = 1 ∑ p k ⩽ n ⌊ p k n ⌋ = p − 1 n − S p ( n ) .
where S p ( n ) S_p(n) S p ( n ) n n n p p p
S p ( n ) = { 1 , if n = 1 S p ( n p ) , if p ∣ n S p ( n − 1 ) + 1 , otherwise . S_p(n)= \begin{cases} 1, & \text {if} n=1 \\ \displaystyle S_p\Big(\frac{n}{p}\Big), & \text {if} p\mid n \\ S_p(n-1)+1, & \text {otherwise}. \end{cases} S p ( n ) = ⎩ ⎨ ⎧ 1 , S p ( p n ) , S p ( n − 1 ) + 1 , if n = 1 if p ∣ n otherwise .
Ex 求 M = ∑ i = 1 n v 5 ( i ! ) \displaystyle M=\sum_{i=1}^{n}v_5(i!) M = i = 1 ∑ n v 5 ( i !) //www.luogu.com.cn/problem/P2388 ))
M = ∑ i = 1 n v 5 ( i ! ) = ∑ i = 1 n ∑ k = 1 5 k ≤ i ⌊ i 5 k ⌋ = ∑ k = 1 5 k ≤ n ∑ i = 1 n ⌊ i 5 k ⌋ = ∑ k = 1 5 k ≤ n [ 5 k + 2 ⋅ 5 k + ⋯ + ( ⌊ n 5 k ⌋ − 1 ) ⋅ 5 k + ⌊ n 5 k ⌋ ( n m o d 5 k + 1 ) ] = ∑ k = 1 5 k ≤ n [ 5 k 2 ⌊ n 5 k ⌋ ( ⌊ n 5 k ⌋ − 1 ) + ⌊ n 5 k ⌋ ( n m o d 5 k + 1 ) ] = ∑ 5 ≤ i = 5 k ≤ n [ i 2 ⌊ n i ⌋ ( ⌊ n i ⌋ − 1 ) + ⌊ n i ⌋ ( n m o d i + 1 ) ] \begin{align} M &= \sum_{i=1}^{n}v_5(i!) = \sum_{i=1}^{n}\sum_{k=1}^{5^k\le i}\bigg\lfloor\dfrac{i}{5^k}\bigg\rfloor = \sum_{k=1}^{5^k\le n}\sum_{i=1}^{n}\bigg\lfloor\dfrac{i}{5^k}\bigg\rfloor \\ &= \sum_{k=1}^{5^k\le n}\bigg[ 5^k +2\cdot5^k +\dots +\bigg(\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor-1\bigg)\cdot5^k +\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor\Big(n\bmod{5^k}+1\Big) \bigg] \\ &= \sum_{k=1}^{5^k\le n}\bigg[\frac{5^k}{2}\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor\bigg(\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor-1\bigg) +\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor\Big(n\bmod{5^k}+1\Big) \bigg] \\ &= \sum_{5\le i=5^k\le n}^{}\bigg[\frac{i}{2}\bigg\lfloor\dfrac{n}{i}\bigg\rfloor\bigg(\bigg\lfloor\dfrac{n}{i}\bigg\rfloor-1\bigg) +\bigg\lfloor\dfrac{n}{i}\bigg\rfloor\Big(n\bmod{i}+1\Big) \bigg] \\ \end{align} M = i = 1 ∑ n v 5 ( i !) = i = 1 ∑ n k = 1 ∑ 5 k ≤ i ⌊ 5 k i ⌋ = k = 1 ∑ 5 k ≤ n i = 1 ∑ n ⌊ 5 k i ⌋ = k = 1 ∑ 5 k ≤ n [ 5 k + 2 ⋅ 5 k + ⋯ + ( ⌊ 5 k n ⌋ − 1 ) ⋅ 5 k + ⌊ 5 k n ⌋ ( n mod 5 k + 1 ) ] = k = 1 ∑ 5 k ≤ n [ 2 5 k ⌊ 5 k n ⌋ ( ⌊ 5 k n ⌋ − 1 ) + ⌊ 5 k n ⌋ ( n mod 5 k + 1 ) ] = 5 ≤ i = 5 k ≤ n ∑ [ 2 i ⌊ i n ⌋ ( ⌊ i n ⌋ − 1 ) + ⌊ i n ⌋ ( n mod i + 1 ) ]
Arithmetic Functions 通俗地讲，input 是 integer 的 function，即 Arithmetic Function。
Completely Multiplicative For all x , y x, y x , y f ( x y ) = f ( x ) f ( y ) f(x y) = f(x) f(y) f ( x y ) = f ( x ) f ( y ) f ( n ) = ∏ p ∣ n [ f ( p ) ] ν p ( n ) \displaystyle f(n) = \prod_{p \mid n} [f(p)]^{\nu_{p}(n)} f ( n ) = p ∣ n ∏ [ f ( p ) ] ν p ( n ) If f f f g g g f ( n k ) f(n^{k}) f ( n k ) [ f ( n ) ] k [f(n)]^{k} [ f ( n ) ] k ( f ⋅ g ) ( n ) = f ( n ) g ( n ) (f \cdot g)(n) = f(n)g(n) ( f ⋅ g ) ( n ) = f ( n ) g ( n ) ( f ∗ g ) ( n ) (f \ast g)(n) ( f ∗ g ) ( n ) Examples :
Unit Function I ( n ) = [ n = 1 ] I(n) = [n = 1] I ( n ) = [ n = 1 ] Identity for Dirichlet convolution, 类比单位矩阵 Power Function id k ( n ) = n k \operatorname{id}_{k}(n) = n^{k} id k ( n ) = n k Constant Function id 0 ( n ) = 1 ( n ) = 1 \operatorname{id}_{0}(n) = 1(n) = 1 id 0 ( n ) = 1 ( n ) = 1 Identity Function id 1 ( n ) = n \operatorname{id}_{1}(n) = n id 1 ( n ) = n Multiplicative For all x ⊥ y x \perp y x ⊥ y f ( x y ) = f ( x ) f ( y ) f(x y) = f(x) f(y) f ( x y ) = f ( x ) f ( y ) f ( n ) = ∏ p ∣ n f ( p ν p ( n ) ) \displaystyle f(n) = \prod_{p \mid n} f(p^{\nu_{p}(n)}) f ( n ) = p ∣ n ∏ f ( p ν p ( n ) ) f ( p ν p ( n ) ) ≠ [ f ( p ) ] ν p ( n ) \displaystyle f(p^{\nu_{p}(n)}) \neq [f(p)]^{\nu_{p}(n)} f ( p ν p ( n ) ) = [ f ( p ) ] ν p ( n ) If f f f g g g f ( n k ) f(n^{k}) f ( n k ) f k ( n ) f^{k}(n) f k ( n ) ( f ⋅ g ) ( n ) = f ( n ) g ( n ) (f \cdot g)(n) = f(n)g(n) ( f ⋅ g ) ( n ) = f ( n ) g ( n ) ( f ∗ g ) ( n ) (f \ast g)(n) ( f ∗ g ) ( n ) Examples :
Divisor Function σ k ( n ) = ∑ d ∣ n d k \displaystyle \sigma_{k}(n) = \sum_{d \mid n} d^{k} σ k ( n ) = d ∣ n ∑ d k 约数个数 (Number of Divisors): τ ( n ) = σ 0 ( n ) = ∑ d ∣ n 1 = ∏ p ∣ n ( ν p ( n ) + 1 ) \displaystyle \tau(n) = \sigma_0(n) = \sum_{d \mid n} 1 = \prod_{p \mid n} \big(\nu_{p}(n) + 1\big) τ ( n ) = σ 0 ( n ) = d ∣ n ∑ 1 = p ∣ n ∏ ( ν p ( n ) + 1 ) 约数和 (Sum of Divisors): σ ( n ) = σ 1 ( n ) = ∑ d ∣ n d = ∏ p ∣ n p ν p ( n ) + 1 − 1 p − 1 \displaystyle \sigma(n) = \sigma_1(n) = \sum_{d \mid n} d = \prod_{p \mid n} \frac{p^{\nu_{p}(n)+1} - 1}{p - 1} σ ( n ) = σ 1 ( n ) = d ∣ n ∑ d = p ∣ n ∏ p − 1 p ν p ( n ) + 1 − 1 Möbius Function μ ( n ) = { 1 , n = 1 0 , ∃ d > 1 , d 2 ∣ n ( − 1 ) ω ( n ) , otherwise \mu(n) = \begin{cases} 1, & n = 1 \\ 0, & \exists d > 1, d^{2} \mid n \\ (-1)^{\omega(n)}, & \text{otherwise} \end{cases} μ ( n ) = ⎩ ⎨ ⎧ 1 , 0 , ( − 1 ) ω ( n ) , n = 1 ∃ d > 1 , d 2 ∣ n otherwise μ = 1 − 1 ⟺ μ ∗ 1 = I ⟺ ∑ d ∣ n μ ( d ) = [ n = 1 ] = I ( n ) \mu = 1^{-1} \iff \mu * 1 = I \iff \displaystyle \sum_{d \mid n} \mu(d) = [n = 1] = I(n) μ = 1 − 1 ⟺ μ ∗ 1 = I ⟺ d ∣ n ∑ μ ( d ) = [ n = 1 ] = I ( n ) ∑ d ∣ n , d ∣ m μ ( d ) = [ n ⊥ m ] \displaystyle \sum_{d \mid n, d \mid m} \mu(d) = [n \perp m] d ∣ n , d ∣ m ∑ μ ( d ) = [ n ⊥ m ] Euler’s Totient Function φ ( n ) = ∑ i = 1 n [ i ⊥ n ] = n ∏ p ∣ n ( 1 − 1 p ) \displaystyle \varphi(n) = \sum_{i=1}^n [i \perp n] = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right) φ ( n ) = i = 1 ∑ n [ i ⊥ n ] = n p ∣ n ∏ ( 1 − p 1 ) 1 ∼ n 1\sim n 1 ∼ n n n n ∑ i = 1 n i [ i ⊥ n ] = n φ ( n ) 2 ( n > 1 ) \displaystyle \sum_{i=1}^{n} i \ [i \perp n] = \frac{n\varphi(n)}{2} \quad (n > 1) i = 1 ∑ n i [ i ⊥ n ] = 2 n φ ( n ) ( n > 1 ) 1 ∼ n 1\sim n 1 ∼ n n n n φ = id ∗ μ ⟺ φ ∗ 1 = id ⟺ ∑ d ∣ n φ ( d ) = n \displaystyle \varphi = \text{id} \ast \mu \iff \varphi \ast 1 = \text{id} \iff \sum_{d \mid n} \varphi(d) = n φ = id ∗ μ ⟺ φ ∗ 1 = id ⟺ d ∣ n ∑ φ ( d ) = n ∑ d ∣ n , d ∣ m φ ( d ) = ( n , m ) \displaystyle\sum_{d \mid n, d \mid m} \varphi(d) = (n, m) d ∣ n , d ∣ m ∑ φ ( d ) = ( n , m ) Additive For all x ⊥ y x \perp y x ⊥ y f ( x y ) = f ( x ) + f ( y ) f(x y) = f(x) + f(y) f ( x y ) = f ( x ) + f ( y ) Example : 不同素因子个数 ω ( n ) \omega(n) ω ( n ) n ≤ 10 9 n \le 10^{9} n ≤ 1 0 9 ω ( n ) \omega(n) ω ( n ) Completely Additive For all x , y x, y x , y f ( x y ) = f ( x ) + f ( y ) f(x y) = f(x) + f(y) f ( x y ) = f ( x ) + f ( y ) Example : 所有素因子个数 (计重) Ω ( n ) \Omega(n) Ω ( n ) Theorems Fundamental Theorem of Arithmetic (FTA). Every integer greater than 1 can be represented as a product of prime numbers in only one way, apart from the order of the factors.
Prime Number Prime Number Theorem. lim n → ∞ π ( n ) n / ln ( n ) = 1 \displaystyle \lim_{n \to \infty} \dfrac{\pi(n)}{n/\ln(n)} = 1 n → ∞ lim n / ln ( n ) π ( n ) = 1 Density of Square-free Integers. The number of square-free integers Q ( n ) Q(n) Q ( n ) n n n lim n → ∞ Q ( n ) n = 6 π 2 = 1 ζ ( 2 ) \displaystyle \lim_{n \to \infty} \dfrac{Q(n)}{n} = \frac{6}{\pi^{2}} = \frac{1}{\zeta(2)} n → ∞ lim n Q ( n ) = π 2 6 = ζ ( 2 ) 1 Chebyshev’s Theorem. For every integer n > 1 n > 1 n > 1 p p p n < p < 2 n n < p < 2n n < p < 2 n Twin Prime Conjecture. There are infinitely many pairs of primes ( p , p + 2 ) (p, p+2) ( p , p + 2 ) Dirichlet’s Theorem on Arithmetic Progressions. For any two coprime positive integers a a a d d d a , a + d , a + 2 d , a + 3 d , … a, a+d, a+2d, a+3d, \dots a , a + d , a + 2 d , a + 3 d , … Green-Tao Theorem. The set of prime numbers contains arbitrarily long arithmetic progressions a , a + d , a + 2 d , a + 3 d , … a, a+d, a+2d, a+3d, \dots a , a + d , a + 2 d , a + 3 d , … Congruences Bézout’s Lemma. a , b ∈ Z ⟹ a,b \in \mathbb{Z} \implies a , b ∈ Z ⟹ x , y ∈ Z x,y \in \mathbb{Z} x , y ∈ Z a x + b y = gcd ( a , b ) ax + by = \gcd(a, b) a x + b y = g cd( a , b ) Fermat’s Little Theorem. p ∤ a ⟹ a p − 1 ≡ 1 ( m o d p ) p \nmid a \implies a^{p - 1} \equiv 1 \pmod p p ∤ a ⟹ a p − 1 ≡ 1 ( mod p ) Euler’s Theorem. a ⊥ n ⟹ a φ ( n ) ≡ 1 ( m o d n ) a \perp n \implies a^{\varphi(n)} \equiv 1 \pmod n a ⊥ n ⟹ a φ ( n ) ≡ 1 ( mod n ) Extend Euler’s Theorem. a b ≡ { a b m o d φ ( n ) , a ⊥ n a b a ⊥̸ n , b ⩽ φ ( n ) a b m o d φ ( n ) + φ ( n ) a ⊥̸ n , b > φ ( n ) ( m o d n ) a^{b} \equiv \begin{cases} a^{b \bmod \varphi(n)}, & a \perp n \\ a^{b} & a \not \perp n, b \leqslant \varphi(n) \\ a^{b \bmod \varphi(n) + \varphi(n)} & a \not \perp n, b > \varphi(n) \end{cases} \pmod n a b ≡ ⎩ ⎨ ⎧ a b mod φ ( n ) , a b a b mod φ ( n ) + φ ( n ) a ⊥ n a ⊥ n , b ⩽ φ ( n ) a ⊥ n , b > φ ( n ) ( mod n ) Lemma. x ≡ x − 1 ( m o d p ) ⟺ x ≡ ± 1 x \equiv x^{-1} \pmod p \iff x \equiv \pm 1 x ≡ x − 1 ( mod p ) ⟺ x ≡ ± 1 Wilson’s Theorem. p ∈ N 2 ⟹ p ∈ P ⟺ ( p − 1 ) ! ≡ − 1 ( m o d p ) p \in \mathbb{N}_{2} \implies p \in \mathbb{P} \iff (p-1)! \equiv -1 \pmod p p ∈ N 2 ⟹ p ∈ P ⟺ ( p − 1 )! ≡ − 1 ( mod p ) 中国剩余定理 (Chinese Remainder Theorem, CRT) Let m i m_i m i coprime x ≡ a i ( m o d m i ) x \equiv a_i \pmod{m_i} x ≡ a i ( mod m i ) M = ∏ i m i M = \prod_{i} m_{i} M = ∏ i m i x ≡ ∑ i a i M i M i − 1 ( m o d M ) x \equiv \sum_{i} a_{i} M_{i} M_{i}^{-1} \pmod{M} x ≡ ∑ i a i M i M i − 1 ( mod M ) M i = M m i M_{i} = \dfrac{M}{m_{i} } M i = m i M M i − 1 M_{i}^{-1} M i − 1 M i M_{i} M i m i m_{i} m i M i M i − 1 ≡ 1 ( m o d m i ) M_{i} M_{i}^{-1} \equiv 1 \pmod{m_{i} } M i M i − 1 ≡ 1 ( mod m i ) Computational Geometry Distance two points x = ( x 1 , x 2 , … , x n ) x = (x_{1}, x_{2}, \dots, x_{n}) x = ( x 1 , x 2 , … , x n ) y = ( y 1 , y 2 , … , y n ) y = (y_{1}, y_{2}, \dots, y_{n}) y = ( y 1 , y 2 , … , y n ) n n n
Minkowski Distance (general) L p ( x , y ) = ∑ i = 1 n ∣ x i − y i ∣ p p Manhattan Distance (diamond) L 1 ( x , y ) = ∑ i = 1 n ∣ x i − y i ∣ Euclidean Distance (circle) L 2 ( x , y ) = ∑ i = 1 n ( x i − y i ) 2 Chebyshev Distance (square) L ∞ ( x , y ) = lim p → + ∞ L p ( x , y ) = max i ∣ x i − y i ∣ \begin{aligned} \text{Minkowski Distance (general)} \qquad & L_{p}(x, y) = \sqrt[p]{\sum_{i=1}^{n} \lvert x_{i} - y_{i} \rvert^{p} } \\ \text{Manhattan Distance (diamond)} \qquad & L_{1}(x, y) = \sum_{i=1}^{n} \lvert x_{i} - y_{i} \rvert \\ \text{Euclidean Distance (circle)} \qquad & L_{2}(x, y) = \sqrt{\sum_{i=1}^{n} (x_{i} - y_{i})^{2} } \\ \text{Chebyshev Distance (square)} \qquad & L_{\infty}(x, y) = \lim_{p \to +\infty} L_{p}(x, y) = \max_{i} \lvert x_{i} - y_{i} \rvert \end{aligned} Minkowski Distance (general) Manhattan Distance (diamond) Euclidean Distance (circle) Chebyshev Distance (square) L p ( x , y ) = p i = 1 ∑ n ∣ x i − y i ∣ p L 1 ( x , y ) = i = 1 ∑ n ∣ x i − y i ∣ L 2 ( x , y ) = i = 1 ∑ n ( x i − y i ) 2 L ∞ ( x , y ) = p → + ∞ lim L p ( x , y ) = i max ∣ x i − y i ∣
Manhattan to Chebyshev Let u = x + y , v = x − y u=x+y, \ v=x-y u = x + y , v = x − y L 1 ( x , y ) = L ∞ ( u , v ) L_1(x, y) = L_\infty(u, v) L 1 ( x , y ) = L ∞ ( u , v )
Proof:
L 1 ( x , y ) = ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ = max { ∣ ( x 1 + y 1 ) − ( x 2 + y 2 ) ∣ , ∣ ( x 1 − y 1 ) − ( x 2 − y 2 ) ∣ } = max { ∣ u 1 − u 2 ∣ , ∣ v 1 − v 2 ∣ } = L ∞ ( u , v ) \begin{aligned} L_1(x, y) &= |x_{1} - x_{2}| + |y_{1}- y_{2}| \\ &= \max\{|(x_{1} + y_{1}) - (x_{2} + y_{2})|, |(x_{1} - y_{1}) - (x_{2} - y_{2})|\} \\ &= \max\{|u_{1} - u_{2}|, |v_{1} - v_{2}|\} \\ &= L_\infty(u, v) \end{aligned} L 1 ( x , y ) = ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ = max { ∣ ( x 1 + y 1 ) − ( x 2 + y 2 ) ∣ , ∣ ( x 1 − y 1 ) − ( x 2 − y 2 ) ∣ } = max { ∣ u 1 − u 2 ∣ , ∣ v 1 − v 2 ∣ } = L ∞ ( u , v )
Chebyshev to Manhattan Let u = x + y 2 , v = x − y 2 u=\dfrac{x+y}{2}, \ v=\dfrac{x-y}{2} u = 2 x + y , v = 2 x − y L ∞ ( x , y ) = L 1 ( u , v ) L_{\infty}(x, y) = L_1(u, v) L ∞ ( x , y ) = L 1 ( u , v )
Proof.
L ∞ ( x , y ) = max { ∣ x 1 − x 2 ∣ , ∣ y 1 − y 2 ∣ } = ∣ x 1 + y 1 2 − x 2 + y 2 2 ∣ + ∣ x 1 − y 1 2 − x 2 − y 2 2 ∣ = ∣ u 1 − u 2 ∣ + ∣ v 1 − v 2 ∣ = L 1 ( u , v ) \begin{aligned} L_{\infty}(x, y) &= \max\{|x_{1}-x_{2}|, |{y_{1}-y_{2}|}\} \\ &= {\bigg|\dfrac{x_{1} + y_{1} }{2}-\dfrac{x_{2} + y_{2} }{2}\bigg| + \bigg|\dfrac{x_{1} - y_{1} }{2}-\dfrac{x_{2} - y_{2} }{2}\bigg|} \\ &= {|u_{1} - u_{2}| + |v_{1} - v_{2}|} \\ &= L_{1}(u, v) \end{aligned} L ∞ ( x , y ) = max { ∣ x 1 − x 2 ∣ , ∣ y 1 − y 2 ∣ } = 2 x 1 + y 1 − 2 x 2 + y 2 + 2 x 1 − y 1 − 2 x 2 − y 2 = ∣ u 1 − u 2 ∣ + ∣ v 1 − v 2 ∣ = L 1 ( u , v )
