Problem
給你一個正整數 $N$ ($1 < N \le10^{18}$)，請你把 $N$ 質因數分解。
注意：大整數分解
Sample Input
|
|
Sample Output
|
|
Solution
2015/07/11 第二版，加速三倍，加快模乘法運算，減少模數利用減法。
|
|
b432. 趣味加分
Problem
背景
廖氏如神 (pcsh710742) 在作業中遇到一題，用手算會算到天昏地暗，而問題是這樣子的：
$a^{13337} \equiv n \mod 2^{64}$其中 $n= 2015 + 2 \times (\text{The last 2 digit of your student ID number})$，請找到 $a < 2^{64}$ 的其中一組解。
問題描述
模數 $2^{64}$ 看起來不大，但對於 Ghz 為 CPU 運算速度單位的電腦而言還是要跑非常久的。因此將問題簡化：
$a^{23333} \equiv n \mod 2^{20}$現在給予一個 $n$，請求出一組 $a$，測資中保證答案唯一。
Sample Input
|
|
Sample Output
|
|
Solution
除了偶數無解外，奇數都至少有一個解。而這一題的題目數據恰好奇數都只有一解，那麼就不必處理多組解或者是字典順序最小的，只要專心找到符合的解即可。
- 暴力建表 $O(2^{20})$ 建完，之後直接查找。
- 篩選正解，依序窮舉從最低位到最高位 (二進制下) 為 0 還是 1，由於次方會不斷地推移，高位結果不影響低位的對應。窮舉時保留低位符合的解，並且不斷地篩選掉不可能的解方案，複雜度 $O(20 k)$，$k$ 是難以估計的數字。
- 快速假解，類似篩選正解的做法，但只保留其中一組解進行，複雜度 $O(20)$。這個解法是有點毛病的，但目前找不到反例。
快速假解
|
|
篩選正解
|
|
b431. 中國餘數
Problem
背景
中國餘數定理 (Chinese Remainder Theorem，簡稱 CRT) 經常是工程學裡面常用的一種轉換域，很多人不知道當初在大學離散數學中學這個做什麼，但是在不少計算的設計都會運用到 CRT。由於電腦 CPU 架構中的運算單位是 32-bits 或者 64-bits (也許在未來會更長)，但值域高達 128-bits 或者 512-bits 以上模擬運算成了麻煩之處。
回顧中國餘數定理 CRT
$$(S): \left\{\begin{matrix} x \equiv a_1 \mod m_1 \\ x \equiv a_2 \mod m_2 \\ \vdots \\ x \equiv a_n \mod m_n \end{matrix}\right.$$- $m_1, m_2, \cdots , m_n$ 任兩數互質，意即 $\forall i \neq j, gcd(m_i, m_j) = 1$
- 對於任意整數 $a_1, a_2, \cdots , a_n$ 方程組 $(S)$ 均有解，意即找得到一個 $x$ 的參數解。
構造法解 CRT
- 設$M = m_1 \times m_2 \times \cdots \times m_n = \prod_{i=1}^{n} m_i$
- 設$M_i = M / m_i$
- 設$t_i = M_i^{-1} \mod m_i<span>$，意即$</span><!-- Has MathJax -->t_i M_i \equiv 1 \mod m_i$
- 方程組 $(S)$ 的通解形式為： $x = a_1 t_1 M_1 + a_2 t_2 M_2 + \cdots + a_n t_n M_n + kM = kM + \sum_{i = 1}^{n} a_i t_i M_i, k \in \mathbb{Z}$
- 若限定 $0 \le x < M$，則 $x$ 只有一解。
很多人會納悶通解為什麼長那樣，原因很簡單，要滿足方程組每一條式子，勢必對於$a_i t_i M_i$ 要滿足$x \equiv a_i \mod m_i$ ，因此 $a_i t_i M_i \equiv a_i (t_i M_i) \mod m_i \equiv a_i \mod m_i$ 成立，但是$\forall i \neq j$，滿足$a_i t_i M_i \equiv a_i (t_i M_i) \mod m_j \equiv 0 \mod m_j$
問題描述
來個簡單運用，來計算簡單的 RSA 加解密，特化其中的數學運算。
$M \equiv C^d \mod n$ $n = p \times q$，其中 $p, q$ 是兩個不同的質數，已知 $C, d, p, q$，請求出 $M$。## Sample Input ##
|
|
Sample Output
|
|
Solution
RSA 可以預先處理
- $c_p = q \times (q^{-1} \mod p)$
- $c_q = p \times (p^{-1} \mod q)$
還原的算法則是 $M = Mp \times c_p + Mq \times c_q \mod N$
由於拆分後的 bit length 少一半，乘法速度快 4 倍，快速冪次方快 2 倍 (次方的 bit length 少一半)，但是要算 2 次，最後共計快 4 倍。CPU 的乘法想必不會用快速傅立葉 FFT 來達到乘法速度為 $O(n \log n)$。
特別小心「 bit length 少一半 」必須在 $gcd(C, p) = 1$ 時才成立，互質機率機率非常高，仍然有不成立的時候，這情況下速度不是加快 400%。請參照一般解。
例如 C = 27522, d = 17132, p = 2, q = 17293，若使用歐拉定理計算 $Mp = C^{d \mod (p-1)} \mod p = 1$ 事實上 $Mp = C^d \mod p = 0$。有一個特性尚未被利用，對於模質數 $p$ 而言，所有數 $x$ 在模 $p$ 下的循環長度 $L | (p-1)$，最後可以套用 $Mp = C^{d \mod (p-1) + (p-1)} \mod p$ 來完成。請參照循環解，如此一來就不必先判斷 $gcd(C, p) = 1$。
番外
但是利用 CRT 計算容易受到硬體上攻擊，因為會造成 $p, q$ 在分解過程中獨立出現，當初利用 $N$ 很難被分解的特性來達到資訊安全，但是卻因為加速把 $p, q$ 存放道不同時刻的暫存器中。
其中一種攻擊，計算得到 $M = Mp \times q \times (q^{-1} \mod p) + Mq \times p \times (p^{-1} \mod q) \mod N$ 當擾亂後面的式子 (提供不穩定的計算結果)。得到 $M' = Mp \times q \times (q^{-1} \mod p) + (Mq + \Delta) \times p \times (p^{-1} \mod q) \mod N$
接著 $(M' - M) = (\Delta' \times p) \mod N$，若要求 $p$ 的方法為 $gcd(M' - M, N) = gcd(\Delta' \times p, N) = p$，輾轉相除的概念呼之欲出，原來 $p$ 會被這麼夾出，當得到兩個 $p, q$，RSA 算法就會被破解。
一般解
|
|
循環解
|
|
b430. 簡單乘法
Problem
背景
在早期密碼世界中， 各種運算都先講求速度，不管是在硬體、軟體利用各種數學定義來設計加密算法就為了加快幾倍的速度，但在近代加密中，加速方法會造成硬體實作攻擊，速度和安全，你選擇哪一個呢。
題目描述
$$a b \equiv x \mod n$$
已知 $a, b, n$，求出 $x$。
Sample Input
|
|
Sample Output
|
|
Solution
利用加法代替乘法避免溢位，加法取模換成減法加快速度。
由於這一題範圍在在 $10^{18}$，用 long long 型態沒有問題，若在 $2^{63}$ 請替換成 unsigned long long。
|
|
b429. 離散對數
Problem
背景
高中時上過對數，了解 $a^x = b$，則 $x = \log_{a}{b}$。這個問題很簡單，但是 log() 又是怎麼運作，當時是用查表法，不久在大學就會學到泰勒級數，藉由電腦運算，計算越多次就能更逼近真正的結果。
離散對數的形式如下：
$$a^x \equiv b \mod n$$
已知 $a, b, n$，通常會設定 $0 \le a, b < n$。這問題的難處在於要怎麼解出 $x$，沒有 log() 可以這麼迅速得知。
為什麼需要離散對數？不少的近代加密算法的安全強度由這個問題的難度決定，例如 RSA 加密、Diffie-Hellman 金鑰交換 … 等，實際運用需要套用許多數論原理。然而，加密機制要保證解得回來，通常會保證 $gcd(a, n) = 1$，讓乘法反元素 (逆元) 存在。
問題描述
$$a^x \equiv b \mod n$$
已知 $a, b, n$，解出最小的 $x$，若不存在解則輸出 NOT FOUND。
Sample Input
|
|
Sample Output
|
|
Solution
解決問題 $y = g^x \mod p$，當已知 $y, g, p$，要解出 $x$ 的難度大為提升，不像國高中學的指數計算，可以藉由 log() 運算來完成，離散對數可以的複雜度相當高，當 $p$ 是一個相當大的整數時，通常會取用到 256 bits 以上，複雜度則會在 $O(2^{100})$ 以上。
實際上有一個有趣的算法 body-step, giant-step algorithm，中文翻譯為 小步大步算法 ，在 ACM-ICPC 競賽中也可以找到一些題目來玩玩，算法的時間複雜度為 $O(\sqrt{p})$，空間複雜度也是 $O(\sqrt{p})$。相信除了這個外，還有更好的算法可以完成。
小步大步算法其實很類似塊狀表的算法，分塊處理，每一塊的大小為 $\sqrt{p}$，為了找尋答案計算其中一塊的所有資訊，每一塊就是一小步，接著就是利用數學運算，拉動數線，把這一塊往前推動 (或者反過來把目標搜尋結果相對往塊的地方推動)。因此需要走 $\sqrt{p}$ 大步完成。
|
|
b433. 中間相遇法
Problem
背景
加密的每一道過程若存在反運算，則存在解密的程序。絕對安全的加密沒有反運算，那解密也是沒有辦法做到的。通常加解密中一定會用到互斥或 (XOR) 運算，從表格來看，單獨看任何一行一列都恰好分配一半的 0、一半的 1。對於密碼來說，明文跟密文的關係，不管知道的明文還是密文的部分，猜中的機率只有 $1/2$，只要位元數一多，猜中的機率近乎 $(\frac{1}{2})^n \cong 0$。
「只用 XOR key 是不行的，再做一次不就回來了嗎？」
「那用循環位移和加法的 overflow 破壞線性結構！」
「但記得要能解密回來哦。」
於是某 M 提供一個簡單的加密運算，明文 $M$，加密金鑰 $key$
- 密文 $C = ((M \text{<<<} key) + key) \text{ XOR } key$
- 明文 $M = ((C \text{ XOR } key) + (\sim key) + 1) \text{>>>} key$
其中每一個運算都在 16-bit CPU 上運作，$\text{<<<}$ 表示循環左移 (circular shift)，$\sim$ 表示 1 補數。
用抽象化表示加解密流程
- $C = E_{key}(M)$
- $M = D_{key}(C)$
問題描述
現在某 M 正用他自己設計的加解密協定跟未來的自己溝通，但發現到這種加解密，如果對方知道某 M 一定會傳送哪一個明文，接著只要匹配密文，窮舉 $O(2^{16})$ 來找到加密金鑰就會破功。
在電影《模仿遊戲》中，德國納粹 Enigma 密碼機，訊息中的結尾一定會附加「希特勒萬歲！(Heil Hitler!)」匹配密文後，窮舉金鑰就能破解。而某 M 常常傳送「萌萌哒！(Moe Moe Ta!)」只需要 $O(2^{16})$ 就能被破解。
於是某 M 強化他的加密協定，希望破解者至少要在 $O(2^{32})$ 的時間內找到，拖延破解時間。
$C = E_{key_2}(E_{key_1}(M))$ $M = D_{key_1}(D_{key_2}(C))$
現在知道某 M 傳送的其中一組 $(C, M)$，請告訴某 M 有多少組 $(key_1, key_2)$ 的可能性。萬萬沒想到，中間相遇法能在 $O(2^{16} \times 16)$ 解決這個問題。
Sample Input
|
|
Sample Output
|
|
Solution
套用中間相遇法$E_{key_1}(M) = D_{key_2}(C)$ 分別對等式兩邊進行計算，查看相碰情況。
複雜度為窮舉所有可能的 $key_1$ 和 $key_2$，若用平衡樹進行碰撞檢查 $O(2^{16} \times 16)$，利用 HASH 可以降到 $O(2^{16})$，由於 $O(2^{16})$ 是記憶體可以宣告的，則直接使用數組來完成。
Hash
|
|
Array
|
|
b428. 凱薩加密
Problem
背景
曾幾何時，基礎題庫已經成了不基礎的題庫。小小新手們寫個題目，不少拿了 TLE、CE 求助無門，就再也不想打開 Zerojudge。高中生哪有寫這麼困難的題目，高中生都不像高中生。在某 M 那個年代寫的題目非常簡單，沒有特別變化處理，更別說多麼高檔的資料結構，暴力算法 (naive algorithm) 就能輕鬆切題。
「年代變了呢，現在的高中生要寫出比大學生的某 M 更困難的題目」
重溫解題的那份初心吧！
題目描述
在西元前就存在的一種加密－凱薩加密為目前最早發現的替換加密 (substitution cipher)。其原理很簡單，將一段明文往替換成往後數的第 $k$ 個英文字母。
若用數學式表示凱薩加密和解密，如下：
加密 $C = E_K(P) = (P + k) \mod 26$
解密 $P = D_K(P) = (C - k) \mod 26$
例如 $k = 3$ 時，發生的情況如下：
明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC
從數學的觀點來看，每一個字母就是一個數字。
A = 0, B = 1, C = 2, …,X = 23, Y = 24, Z = 25
Sample Input
|
|
Sample Output
|
|
Solution
只需要看第一個字符的變換方式即可。
|
|
POJ 1811 - Prime Test
Problem
給一個大整數 $N \le 2^{54}$，判斷是否為質數，若不是則進行因數分解，並且輸出最小的質因數。
備註：大整數分解不可使用一般的 $O(\sqrt{N})$ 算法完成。
Sample Input
|
|
Sample Output
|
|
Solution
以下的寫法還不是最快的，而且沒有加上最小質因數的剪枝。若在 pollard-rho 算法中，使用 Brent’s algorithm 取代 Floyd’s algorithm 進行環偵測，同時減少模數使用會變得更快 (常數上)。
討論區提供卡邁克爾數 (Carmichael Number)，讓費馬素性檢驗 (Fermat primality test) 判斷失誤，若用盧卡斯-萊默檢驗法 (Miller–Rabin primality test) 則不受影響。這讓我想到寫過鄒賽爾數 (Zeisel Number) 生成，由數個質數構成大數 $N$ 能測試更多的效能瓶頸吧。
|
|
a761. 罐頭的記憶體
Problem
模擬作業系統的 dynamic memory allocation，
- 宣告連續一段記憶體配置給某個程序，並且標記辨識碼。
- 若宣告失敗，則輸出碰撞區域中，辨識碼最小的數字。
- 詢問記憶體存取時，是否合法，若合法輸出程序的辨識碼。
Sample Input
|
|
Sample Output
|
|
Solution
溫馨提示：此題的測資隨機，單純離散化套用二分查找，編號最小使用線性搜索即可通過。by 蔡神 asas
儘管直觀作法可以通過，來討論看看別種作法吧。
- 線段樹 + 延遲標記 + 離線處理
離散結果最多有 $O(N + Q)$ 的離散點，單筆操作複雜度為 $O(\log Q)$，空間複雜度 $O(Q)$，空間消耗量相較於其他算法最多 (附加延遲標記的使用)。 - 分塊算法 + 離線處理
利用分塊 Unrolled Linked List 的快取優勢來降複雜度，空間複雜度仍然是 $O(Q)$，單筆操作複雜度為 $O(\sqrt{Q})$。空間複雜度的常數比線段樹少一半以上，別忘詢問離線是共同的空間成本。 - 分塊在線
直接宣告 $O(2^{32})$ 進行配置，因此分塊大小為 $O(\sqrt{2^{32}})$。將配置連續區段用區間 $[l, r, pid]$ 的方式儲存在塊之中，用一個平衡樹維護每一個塊的狀態。由於要輸出編號最小的，詢問複雜度至少為 $O(65536)$，為了加速詢問可以利用剪枝 (塊的最小值仍大於當前的答案) 來完成。空間複雜度跟實際情況有關，這一做法在當前數據中是最快，記憶體最小的一種辦法，因為在線很多詢問點是沒必要實際存在的。
由於這一題沒有釋放記憶體操作，從均攤上可以清楚，分塊離線的修改離散點的次數最多為 $O(Q)$，也就是每一個點均被塗色僅僅一次，剩下就是在詢問上加速。
線段樹
|
|
分塊離線
|
|
分塊在線
|
|
b436. 圖片的梯度再進化
Problem
除了索貝爾運算 Sobel operator，還有如 Prewitt operator、Kirsch operator … 等，來進行邊擷取。
Sample Input
|
|
Sample Output
|
|
Solution
比較麻煩是在處理邊緣擴充，寫一個函數去特判延伸的 pixel 位置。
|
|