殘龍的數學筆記

文章目录

老實說了吧，這篇東西是個大坑，反正我根本沒準備填。
你們如果有靠譜的資料，可以貼在下面供我參考，謝謝。

數論

最大公約數

https://en.wikipedia.org/wiki/Greatest_common_divisor

歐幾里德算法

https://en.wikipedia.org/wiki/Euclidean_algorithm

$ \begin{eqnarray} gcd(a,b) = \begin{cases}
a, & b = 0 \cr
gcd(b, a \bmod b), & otherwise
\end{cases} \end{eqnarray} $

令 $ r = gcd(a,b) $
則 $ r \mid a, r \mid b $
故 $ r \mid (a - b) $
引 $ r \mid (a - kb)
\Rightarrow r \mid (a - \lfloor \frac{a}{b} \rfloor b)
\Rightarrow r \mid (a \bmod b) $
故 $ gcd(a,b) \equiv gcd(b, a \bmod b) $

擴展歐幾里德算法

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

若 $ a, b, gcd(a,b) = 1 $，求 $ax + by = 1$

乘法逆元

https://en.wikipedia.org/wiki/Multiplicative_inverse

费马小定理

https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

若 $p$ 是素數，$a$ 是正整數，則：$a^p \equiv a \pmod{p}$。
若 $p$ 是素數，$a$ 是正整數且不能被 $p$ 整除，則：$a^{p-1} \equiv 1 \pmod{p}$。

歐拉定理

https://en.wikipedia.org/wiki/Euler%27s_theorem

若 $gcd(p, a)$ = 1，則：$a^{\phi(p)} \equiv 1 \pmod{p}$。$\phi(n)$ 是歐拉函數。

逆元定義

若 $ax \equiv 1 \pmod{p}$，則稱 $x$ 爲 $a$ 模 $p$ 的逆元。
構造 $ax + py = 1$，則x可以用擴展歐幾里德算法求得；
若 $p$ 是質數，$a^{p-2} \equiv x \pmod{p}$。

接下來講實踐中的三個小trick。

編程技巧

Q：教練，我不想求逆元！
A：可以通過以下性質來避開。

若 $b | a$，則：$\frac{a}{b} \bmod p = \frac{a \bmod pb}{b}$

證明：
$ \begin{align*}
& \because \frac{a}{b} \equiv y \pmod{p} \\
& \Rightarrow \frac{a}{b} = px + y \\
& \Rightarrow a = pbx + by \\
& \Rightarrow a \bmod pb = by \\
& \Rightarrow \frac{a \bmod pb}{b} = y \\
& \therefore \frac{a}{b} \bmod p = \frac{a \bmod pb}{b} \\
\end{align*} $

Q：如何對 $1!$ 到 $p-1!$ 的逆元高效打表？
A：

fac[0] = 1;
rep(i, 1, p) fac[i] = fac[i-1] * i % p;
inv[p-1] = csl::inv(fac[p-1]);
rrep(i, 1, p) inv[i-1] = inv[i] * i % p;

Q：那 $1$ 到 $p-1$ 不能這樣玩啊！
A：

1 2	inv[1] = 1; rep(i, 2, p) inv[i] = (p - p / i) * inv[p % i] % p;

證明：
對於 $x$ 的逆元 $inv(x)$，滿足 $ x \cdot inv(x) \equiv 1 \pmod{p}$
由於 $p = ax + b$，令 $a = \lfloor \frac{p}{x} \rfloor, b = p \bmod x$
所以 $x = (p-b) / a = -b / a \pmod{p}$，$inv(x) = -a/b = -a \cdot inv(b) \pmod{p}$

中國剩餘定理

https://en.wikipedia.org/wiki/Chinese_remainder_theorem

已知 $ M = \prod m_{i} $，$ m_{i} \text{ is a prime number} $，$ S \equiv a_{i} \pmod{m_{i}} $，求 $ S $

先看 $ S \equiv a_{i} \pmod{m_{i}} $ 可以轉化爲 $ S + m_{i}y = a_{i} $，這個公式仍然不利於求解
聯想到 $ ax + by = gcd(a, b) $ 的形式，可以用擴展歐幾里德搞一搞
不妨令 $ M_{i} = \frac{ M }{ m_{i} } $，構造 $ M_{i}x + m_{i}y = gcd(M_{i}, m_{i}) = 1 $
這樣搞的好處都有啥？誰說對了csy就給他（非金坷拉
化成 $ M_{i}x \equiv 1 \pmod{m_{i}} $，$ \forall j \neq i, M_{i}x \equiv 0 \pmod{m_{j}} $
顯然 $ x $ 是 $ M_{i} $ 關於 $ m_{i} $ 的逆元，發現並不一定要用 $ exgcd $，我們記爲 $ x_{i} $
那麼 $ a_{i}M_{i}x_{i} \equiv a_{i} \pmod{m_{i}} $，$ S \equiv \sum a_{i}M_{i}x_{i} \pmod{M}$。
本質即求出對於 $m_{i}$ 相互獨立的各項 $ a_{i}M_{i}x_{i}$，然後對其進行合併即可。

一種巧妙的實現：

T M = m[0], R = a[0];
rep(i, 1, n) {
  T mi = m[i], ri = a[i];
  T g = csl::gcd(M, mi);
  if ((R - ri) % g != 0) { cout << "Impossible" << endl; return; }
  if (csl::gcd(M / g, g) == 1) M /= g; else mi /= g;
  R = R * mi * csl::pow(T(1), mi, M - 2, M) + ri * M * csl::pow(T(1), M, mi - 2, mi);
  M *= mi, R %= M;
}
cout << R << endl;

容斥原理

https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

這部分內容姑且放在反演的前面，給讀者壓壓驚。
私以爲，這是組很美妙的公式，如同陰陽兩魚相互糾纏。

定義：
$ g(A) = \sum\limits_{S : S \subseteq A} f(S) $
$ f(A) = \sum\limits_{S : S \subseteq A} (-1)^{|A| - |S|} g(S) $

證明：
$ \begin{align*}
& \because g(A) = \sum\limits_{S : S \subseteq A} f(S) \\
& \therefore \sum\limits_{S : S \subseteq A} (-1)^{|A| - |S|} g(S) \\
& = \sum\limits_{S : S \subseteq A} (-1)^{|A| - |S|} \sum\limits_{T : T \subseteq S} f(T) \\
& = \sum\limits_{T : T \subseteq A} f(T) \sum\limits_{R : R \subseteq A - T} (-1)^{|R|} \\
& = \sum\limits_{T : T \subseteq A} f(T) \sum\limits_{k = 0}^{|A - T|} \binom{|A - T|}{k} (-1)^k \\
& = \sum\limits_{T : T \subsetneqq A} f(T) (1 + (-1))^{|A - T|} + \sum\limits_{T : T \subseteqq A} f(T) (-1)^0 \\
& = 0 + f(A) = f(A) \\
\end{align*} $

積性函數

https://en.wikipedia.org/wiki/Multiplicative_function

定義：
$ f(1) = 1 $ 且 $ \forall gcd(a,b) = 1, f(ab) = f(a) f(b) $
當 $ \forall a,b $ 都滿足 $ f(ab) = f(a) f(b) $ 時，稱爲完全積性函數。

$ Id_{k}(n) $ : $ Id_{k}(n) = n^k $ 完全積性
- $k = 0$ 時，有 $ 1(n) = 1 $
- $k = 1$ 時，有 $ Id(n) = n $
$ \epsilon(n) $ : $ \epsilon(n) = \begin{cases} 1, & n = 1 \cr 0, & \text{otherwise} \end{cases} $

狄利克雷卷積

https://en.wikipedia.org/wiki/Dirichlet_convolution

定義：
$ (f * g)(n) = \sum\limits_{d|n} f(d)g(\frac{n}{d}) $

交換律：$ f * g = g * f $
結合律：$ (f * g) * h = f * (g * h) $
分配率：$ f * (g * h) = f * g + f * h $
$ f = f * \epsilon = \epsilon * f $
$ f * f^{-1} = \epsilon $
$ f^{-1}(n) = \frac{-1}{f(1)}\sum\limits_{d|n,n \neq d} f(\frac{n}{d}) f^{-1}(d) $

歐拉函數

https://en.wikipedia.org/wiki/Euler%27s_totient_function

一般用 $ phi(n) $ 或者 $ \phi(n) $ 表示，是個不完全積性函數。

若 $ n = \prod\limits_{i = 1}^{m} p_i^{k_i} $，
則 $ \phi(n) = n \prod\limits_{i = 1}^{m} (1 - \frac{1}{p_i}) $

莫比烏斯函數

https://en.wikipedia.org/wiki/M%C3%B6bius_function

一般用 $ mu(n) $ 或者 $ \mu(n) $ 表示，是個不完全積性函數。

若 $ n = \prod\limits_{i = 1}^{m} p_i^{k_i} $，
則 $ \mu(n) = \begin{cases}
1, & n = 1 \cr
0, & \exists k_i > 1 \cr
(-1)^m, & \text{otherwise}
\end{cases} $

反演公式

莫比烏斯反演

https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula

$ \sum\limits_{d|n} \phi(d) = Id(n) \Rightarrow \phi * 1 = Id $
$ \sum\limits_{d|n} \mu(d) = \epsilon(n) \Rightarrow \mu * 1 = \epsilon $

$ \begin{align*}
& \because \mu * 1 = \epsilon \\
& \therefore \phi(n) \\
& = \sum\limits_{i = 1}^{n} \epsilon(gcd(i,n)) \\
& = \sum\limits_{i = 1}^{n} \sum\limits_{d | gcd(i,n)} \mu(d) \\
& = \sum\limits_{i = 1}^{n} \sum\limits_{d | i \wedge d | n} \mu(d) \\
& = \sum\limits_{d | n} \mu(d) \frac{n}{d} \\
& = (\mu * Id)(n)
\end{align*} $

按這思路，顯然得證 $ \sum\limits_{i = 1}^{n} i \cdot \epsilon(gcd(i,n)) = \frac{n}{2} (\mu * 1 + \mu * Id)(n) = \frac{n}{2} (\epsilon + \phi)(n) $，即[1,n]中與n互質的數之和。
[2015.12.03] 顺便补充下平方和的结论： $ \sum\limits_{i = 1}^{n} i^2 \cdot \epsilon(gcd(i,n)) = \frac{n^2}{3} \phi(n) + \frac{n^2}{2} \epsilon(n) + \frac{n}{6} \sum\limits_{d | n} \mu(d) d $

如 $ \phi * 1 = Id $，$ \mu * Id = \phi $；
又 $ \epsilon * 1 = 1 $，$ \mu * 1 = \epsilon $；
顯然能得出莫比烏斯反演公式 $ f * 1 = F $，$ \mu * F = f $
亦可以寫作：
$ F(n) = \sum\limits_{d | n} f(d) $
$ f(n) = \sum\limits_{d | n} \mu(\frac{n}{d}) F(d) $

證明：
$ \begin{align*}
& \because f * 1 = F \\
& \therefore (\mu * F)(n) \\
& = \sum\limits_{d | n} \mu(d) F(\frac{n}{d}) \\
& = \sum\limits_{d | n} \mu(d) \sum\limits_{d’ | \frac{n}{d}} f(d’) \\
& = \sum\limits_{d’ | n} f(d’) \sum\limits_{d | \frac{n}{d’}} \mu(d) \\
& = \sum\limits_{d’ | n} f(d’) \epsilon(frac{n}{d’}) \\
& = f(n)
\end{align*} $

二項式反演

對於 $ 0 ^ n $ 的二項式展開：
$ \sum\limits_{i = 0}^{n} (-1)^i \binom{n}{i} = (1 + (-1))^{n} $
然後是個組合數學的小trick：
$ \binom{n}{i} \binom{i}{k} = \frac{n!}{(n-i)!} \frac{1}{k!(i-k)!} = \frac{n!}{k!(n-k)!} \frac{(n-k)!}{(n-i)!(i-k)!} = \binom{n}{k} \binom{n-k}{i-k} $

既然都這樣惹，再隨便推導下二項式的反演吧。
$ \begin{align*}
& \because F(n) = \sum\limits_{i = 0}^{n} \binom{n}{k} f(i) \\
& \therefore \sum\limits_{i = 0}^{n} (-1)^{n-i} \binom{n}{i} F(i) \\
& = \sum\limits_{i = 0}^{n} (-1)^{n-i} \binom{n}{i} \sum\limits_{k = 0}^{i} \binom{i}{k} f(k) \\
& = \sum\limits_{k = 0}^{n} f(k) \sum\limits_{i = k}^{n} (-1)^{n-i} \binom{n}{i} \binom{i}{k} \\
& = \sum\limits_{k = 0}^{n} \binom{n}{k} f(k) \sum\limits_{i = k}^{n} (-1)^{n-i} \binom{n-k}{n-i} \\
& = \sum\limits_{k = 0}^{n} \binom{n}{k} f(k) (1 + (-1))^{n - k} \\
& = 0 + f(n) = f(n)
\end{align*} $

遞推

a[n] = a[n-1]^2 - 2

$ a_{n} = a_{n-1} ^ 2 - 2 $
令 $ a_{0} = x + \frac{1}{x} $
則 $ a_{n} = x ^ {2^n} + \frac{1}{x^{2^n}} $

a[n] = p⋅a[n-1] + q⋅a[n-2]

$ a_{n} = p⋅a_{n-1} + q⋅a_{n-2} $
特徵方程 $ x ^ 2 = p x + q $，求得 $ \alpha \beta $。
若 $ \alpha \neq \beta $，則 $ a_{n} = c_{1} \alpha ^ n + c_{2} \beta ^ n $；
若 $ \alpha = \beta $，則 $ a_{n} = (c_{1} + n c_{2}) \alpha ^ n $。
求得 $ c_{1}, c_{2} $，求得 $ p, q $，即求得 $ a_{n} $。

(a+√b)^n

$ S_{n} = \lceil (a + \sqrt{b}) ^ {n} \rceil $
構造 $ (a + \sqrt{b}) ^ {n} + (a - \sqrt{b}) ^ {n} $
$ \because 0 < a - \sqrt{b} < 1 $，
且二項式展開、合併同類項後，只可能有 $ \sqrt{b} ^ {2i} = b ^ i $
$ \therefore S_{n} = (a + \sqrt{b}) ^ {n} + (a - \sqrt{b}) ^ {n} $
$ S_{n} ⋅ ((a + \sqrt{b}) + (a - \sqrt{b})) $
$ =
(a + \sqrt{b}) ^ {n+1} +
(a - \sqrt{b}) ^ {n+1} +
(a + \sqrt{b}) (a - \sqrt{b}) ((a + \sqrt{b}) ^ {n-1} + (a - \sqrt{b}) ^ {n-1}) $
$ = S_{n+1} + (a ^ 2 - b) S_{n-1} $
移項得 $ S_{n+1} = 2a S_{n} + (b - a ^ 2) S_{n-1} $

也可以直接構造上一節 “a[n] = p⋅a[n-1] + q⋅a[n-2]” 的形式，
特徵根 $ a - \sqrt{b}, a + \sqrt{b} $，$ p = 2a, q = b - a ^ 2 $
輕鬆得 $ S_{n+1} = 2a S_{n} + (b - a ^ 2) S_{n-1} $

浮點

卡翰求和算法

https://en.wikipedia.org/wiki/Kahan_summation_algorithm

對浮點序列求 $ \sum a_i $ 減小過程中的誤差

function KahanSum(input)
  var sum = 0.0
  var c = 0.0
  for i = 1 to input.length do
    var y = input[i] - c
    var t = sum + y
    c = (t - sum) - y
    sum = t
  return sum

牛頓迭代法

牛頓迭代法（Newton Method）：https://en.wikipedia.org/wiki/Newton%27s_method

對 $ \sqrt{S} $ 構造 $ f(x) = x ^ 2 - S = 0 $
有 $ x_{n+1}
= x_{n} - \frac{ f(x_{n}) }{ f’(x_{n}) }
= x_{n} - \frac{ x_{n}^{2} - S }{ 2x_{n} }
= \frac{1}{2} (x_{n} + \frac{S}{x_{n}}) $

Fate / Unlimited Darkness

命運 / 無盡長夜