柊四千的倉庫

設 $p$ 為質數且 $a \in \mathbb{Z}$。考慮問題： 是否存在 $r \in \mathbb{Z}$ 使得 $r^2 \equiv a\ (\operatorname{mod}p)$？ 如果這樣的 $r$ 存在，有沒有好的方法找？ 如果第一個問題的答案是肯定的且 $p\nmid a$，我們說 $a$ 是 $p$ 的 二次剩餘 (quadratic residue)；如果第一個問題的答案是否定的，則說 $a$ 是 $p$ 的 二次非剩餘 (quadratic nonresidue)。 當 $p = 2$ 或 $a \equiv 0$ 時上面兩個問題都是 trivial；以下假定 $p \geq 3$ 且 $a \not\equiv 0$。透過觀察 $x^2-r^2 = (x-r)(x+r)$ 且 $r \neq -r$，我們發現 $a$ 可以寫成 $r^2$ 若且唯若方程式 $x^2-a = 0$ 在 $\mathbb{Z}_p$ 下恰有兩相異根。這代表恰有 $\frac{p-1}{2}$ 個 $\mathbb{Z}_p^\times$ ($\mathbb{Z}_p$ 的乘法群) 裡的元素能被開根號，而另外 $\frac{p-1}{2}$ 個 $\mathbb{Z}_p^\times$ 裡的元素不能被開根號。又，費馬小定理指出，對於所有的 $x \in \mathbb{Z}_p^\times$，均有 \[ x^{p-1} -1 = (x^\frac{p-1}{2}-1)(x^\frac{p-1}{2}+1) = 0 \] 若 $a = r^2$，則 $a^\frac{p-1}{2}-1 = r^{p-1}-1 = 0$。因為方程式 $x^\frac{p-1}{2}-1 = 0$ 最多只能有 $\frac{p-1}{2}$ 個根，我們得到了以下的定理： [定理] 設 $p \geq 3$ 為一奇質數且 $a \in \mathbb{Z}_p^\times$，則 $a$ 是 $p$ 的二次剩餘若且唯若 $a^\frac{p-1}{2} = 1$。 $a$ 是 $p$ 的二次非剩餘若且唯若 $a^\frac{p-1}{2} = -1$。 至此第一個問題 $O(\log p)$ 時間複雜度圓滿解決。 為了接下來的討論方便，這邊介紹 勒讓德符號 (Le...

一棵樹有「拔掉任一非葉節點便不連通」的良好性質，可以幫助我們用 DP 和 divide-and-conquer 解決問題，例如 POJ 1741 和 TIOJ 1647 。這篇假定你知道怎麼把 POJ 1741 做到 $O(n(\log n)^2)$ 的時間複雜度 (如果你不知道也沒關係，google "POJ 1741" 就有很多資料了 XD)。我們沿用 先前 的定義，把一張點數和邊數相等的連通近圖 ( pseudograph ) 稱作一隻水母。再次提醒，水母並不是正式名稱 (我找不到正式名稱 orz)。 考慮這個問題：給定一隻大小為 $n$ 的水母 $J = (V, E)$，邊有正權重，請求出 $J$ 的 $K$-近對個數。一個 $K$-近對的定義是距離不超過 $K$ 的 (無序) 點對。觀察到一隻水母其實是由頭部 (環) 和數條觸手 (樹) 組成。設頭部由點 $t_0, t_1, \ldots, t_{m-1}$ 組成，從 $t_i$ 長出的觸手為 $T_i$。我們把 $K$-近對 $(u, v)$ 分成兩種：$u, v$ 屬於同一條觸手 ($\alpha$ 型)、$u, v$ 屬於不同條觸手 ($\beta$ 型)。只要在每條觸手上跑 POJ 1741，就能求出 $\alpha$ 型 $K$-近對個數了。至於 $\beta$ 型，做法是對於每個點 $v$，統計有幾個點 $u$ 滿足 $u$ 和 $v$ 不在同一條觸手上 $u, v$ 的距離 $d(u, v) \leq K$ 我們用上圖來做說明。設邊 $(t_i, t_{i+1})$ 的權重為 $w_{i+1}$，$s_i := w_1 + \ldots + w_i$ 為「從 $t_0$ 開始，順著 $t_0, t_1, t_2, \ldots$ 的方向，走 $i$ 條邊的里程數」(為了方便，不該超過 $m-1$ 的那些索引值，一旦超過 $m-1$ 就自動對 $m$ 取模)。設 \[ \begin{cases} u \in T_j, d_u := d(u, t_j),\\ v \in T_i, d_v := d(v, t_i), \end{cases} \] 則 $d(u, v)$ 就是 $d_u+d_v+(s_i-s_j)$?! 當然我們沒有這麼好的事情，因為 有...

前言 要計算兩個大數的乘積，可以先把這兩個大數轉成兩個多項式，計算它們的乘積，再轉回大數，時間複雜度 $O(n\log n)$；然而，大數除法和多項式除法可說是完全不一樣的問題。以下要介紹如何利用 牛頓法 把除法問題轉化成乘法問題，並利用倍增 (doubling) 來得到 $O(n\log n)$ 的除法演算法。 本文內容大致上只是把之前我寫的 這篇 document 換成中文，但一些證明以及虛擬碼 (pseudocode) 則省略。另，實作部分可以參考我在 github 上的 大數模板 ，讀者也可以在 ZJ b960 測試自己的程式。 動機 以下設 $\xi$ 和 $\eta$ 都是 $A$ 進位正整數，其中 $A \geq 9$，$\xi \geq \eta$，且 $\xi$ 和 $\eta$ 的長度分別為 $m$ 和 $n$，目標求出 $\lfloor\xi/\eta\rfloor$ 的 $A$ 進位表示。因為 \[\xi/\eta = \xi\times 1/\eta\] 如果我們能把 $1/\eta$ 算得夠精確，就能把除法問題轉換成乘法問題。我們希望能找到某個 $x \leq 1/\eta$ 使得 \begin{equation}\label{goal}\lfloor\xi/\eta\rfloor-1 \leq \lfloor\xi x\rfloor \leq \lfloor\xi/\eta\rfloor\end{equation} 不難發現只要 $x$ 滿足 \begin{equation}\label{tol1}0 \leq 1/\eta-x \leq A^{-m}\end{equation} 就有 \[\xi/\eta-\xi x = \xi(1/\eta-x) \leq A^m\cdot A^{-m} = 1\] 也就是 $(\ref{goal})$ 會成立。接下來我們把目標放在找到 $x$ 滿足 $(\ref{tol1})$。 牛頓法 考慮函數 $f(x) := \frac{1}{x} - \eta$。我們找一個 $x_0 \in (0, \frac{1}{\eta}]$，並對於所有的 $k \geq 0$，令 \[x_{k+1}\gets x_k - \frac{f(x_k)}{f'(x_k)} = x_k(2...

整數的加減乘除四種運算，無論是在國小算術或是在程式設計中，除法都比其他三種運算來得麻煩。舉例來說，假定我們想動手算 $1650794238\div 26451$，長除法的第一步是 我們必須猜出 $\Box$ 內要填的數字，而這正是除法計算痛苦的來源。因為我們沒有表可以查，只能猜一個數字 $\alpha$，放入 $\Box$ 中，看看 $165079 - 26451\alpha$ 是否介於 $0$ 到 $26450$ 之間，而如果不幸猜錯，還得重猜並重新計算一次乘法和減法。 我們把這個猜商問題寫得再清楚一點：給定兩個 $b$ 進位的整數 \[\begin{cases}\xi = x_{n-1}\ldots x_1x_0= x_{n-1} b^{n-1} + \ldots + x_1b + x_0,\\\eta = y_{n-1}\ldots y_1y_0= y_{n-1} b^{n-1} + \ldots + y_1 b + y_0,\end{cases}\] 其中 $0 \leq x_i \leq b-1$ 對於所有的 $0 \leq i \leq n-2$，而 $x_{n-1} \geq 0$ (可以超過 $b-1$，如上面的例子 $b=10, n=5$ 而 $a_4 = 16$)。 $0 \leq y_i \leq b-1$ 對於所有的 $0 \leq i \leq n-1$，且 $y_{n-1} \neq 0$。 $\lfloor\xi/\eta\rfloor \leq b-1$。 目標找出 $a := \lfloor\xi/\eta\rfloor$。有鑑於網路上多數的大數長除法 code，猜商步驟亂寫 (無誤)，我決定在這篇導正視聽 (?)，介紹一個保證在 $O(1)$ 次內猜到 $a$ 的策略。 策略一：枚舉 $a = 0, 1, \ldots, b-1$ 最糟情況猜商次數 $\Theta(b)$，不解釋。 策略二：在 $0, 1, \ldots, b-1$ 之間做二分搜找出 $a$ 這是策略一的簡單改良，猜商次數 $\Theta(\log b)$，一樣不解釋。 策略三：利用 $x_{n-1}$ 和 $y_{n-1}$，縮小策略二的二分搜範圍 想法是這樣的：因為 \[\begin{cases}x_{n-1}b...

多項式乘法常常在一些計數問題上出現，例如 UVa 12298 或  ICPC 5705 。多項式除法雖然比乘法冷門，也是有一些應用的。 問題一：給定 $n-1$ 次複係數多項式 $f(z)$ 和 $n$ 個點 $z_1, \ldots, z_n \in \mathbb{C}$，在 $O(n(\log n)^2)$ 時間內求出 $f(z_1), \ldots, f(z_n)$。 這題出自 CLRS 上的習題。設 $1 \leq l \leq r \leq n$ 並考慮 \[p(z; l, r) := \prod_{k=l}^r(z-z_k) = (z-z_l)\ldots(z-z_r)\] 觀察到 $f(z)$ 在 $z = z_l, \ldots, z_r$ 上的值，和 $f(z)\operatorname{mod}p(z; l, r)$ 在 $z = z_l, \ldots, z_r$ 上的值相同。假定 $p(z; 1, \lfloor n/2\rfloor)$ 和 $p(z; \lfloor n/2\rfloor+1, n)$ 為已知，我們可以分別計算 $f(z)\operatorname{mod}p(z;1, \lfloor n/2\rfloor)$ 在 $z = z_1, \ldots, z_{\lfloor n/2\rfloor}$ 的值 $f(z)\operatorname{mod}p(z; \lfloor n/2\rfloor+1, n)$ 在 $z = z_{\lfloor n/2\rfloor+1}, \ldots, z_n$ 的值 這樣的 divide and conquer 時間複雜度是 $T(n) = 2T(n/2) + O(n\log n) = O(n(\log n)^2)$。 那麼要怎麼求出過程中需要的 $p(z; l, r)$ 們呢？回想一下，計算 $p(z; 1, n) = p(z;1, \lfloor n/2\rfloor)p(z; \lfloor n/2\rfloor+1, n)$ 有一個顯然的 D&C 做法，時間複雜度也是 $O(n(\log n)^2)$，且中間過程算到的 $p(z; l, r)$ 們正好就是前一個 D&C 所需要的 $p(z; l, r)$ 們。這樣...

計算兩個不超過 $n$ 次的複係數一元多項式 $f(x)$ 和 $g(x)$ 的乘積，可以藉由 FFT (Fast Fourier Transform, 快速傅立葉變換) 在 $O(n\log n)$ 時間內求得。更一般的情形，設 $R$ 為一個環且 $f(x), g(x) \in R[x]$，則 $f(x)g(x)$ 可以用 Karatsuba 演算法 在 $O(n^{\log_23})$ 時間內求得，也比 naïve 演算法的 $O(n^2)$ 快。假設多項式乘法的時間複雜度是 $O(M(n))$，這篇將介紹如何在 $O(M(n))$ 時間內計算 $f(x)\div g(x)$ 的商式和餘式。 先定義好我們的問題：設 $R$ 為一個有 $1$ 的環，$f(x), g(x) \in R[x]$ 滿足 $\deg f = n$ $g(x) \neq 0, \deg g = m \leq n$ $g$ 的 $x^m$ 項係數為 $1$ 我們要找出 $q(x), r(x) \in R[x]$ 使得 $f(x) = q(x)g(x) + r(x)$ $\deg r < m$ 不難從長除法證明 $q$ 和 $r$ 存在且唯一。接著，引入反轉算子 $\mathscr{R}: R[x] \to R[x]$，定義對於所有的 $h(x) \in R[x]$， \[(\mathscr{R}h)(x) = \begin{cases}0,&\text{if }h(x) = 0,\\x^ph(\frac{1}{x}),&\text{if }\deg h = p.\end{cases}\] 事實上，若 $h(x) = \alpha_0 + \sum_{i=1}^p\alpha_ix^i \neq 0$，則 $(\mathscr{R}h)(x) = \alpha_p+\sum_{i=1}^p\alpha_{p-i}x^i$。這樣一來，就有 \[(\mathscr{R}f)(x) = \begin{cases}(\mathscr{R}q)(x)\cdot(\mathscr{R}g)(x),&\text{if }r(x) = 0,\\(\mathscr{R}q)(x)\cdot(\mathscr{R}g)(x)+x^{n-\d...