PKU 3696 The Luckiest Number

題意：
給定 L
求 集合 { 8, 88, 888, ... ,888888, ... } 當中 能整除 L 的最小的一個數字
列印該數的長度

---

算法 ── 思路：
設該數為 88....8，則有方程：
　　8 × 11....1 ≡ 0 (mod L) -----------(1)

設 g := (8, L)，得：
　　8/g × 11....1 ≡ 0 (mod L/g) -----------(2)

Case 0: L/g = 1
...

Case 1: L/g 整除 2 或/和 整除 5
11....1 顯然不能整除 2 或/和 整除 5 ⇒ 無解

Case 2: 其他情況
由於 (8/g, L/g) = 1，(2) 可以化簡為：
　　11....1 ≡ 0 (mod L/g) -----------(3)

---

以下為最關鍵的一步！

(3) × 9：
　　99....9 ≡ 0 (mod 9L/g) -----------(4)

令 z := 9L/g， 重寫(4)：
　　10^x = 1 (mod z) -----------(5)

---

基本上，當導出式子 (5) 後，答案經已呼之欲出（好似係）
不過... 還需要多一點點數論知識：

── 歐拉Phi函數！！

在 Case 2 的前提下，可知 (10, 9L/g) = 1
我們可以直接應用 歐拉定理 (Euler's Theorem)：
[實為 費馬小定理 (Fermat's Little Theorem) 的推廣]

定理 1
　　若 (a,n) = 1 ， 則 a^Φ(n) ≡ 1 (mod n)

可知 x₀ = Φ(z) 滿足方程 (5)
即 Φ(z) 其中一個解

---

那麼，是否在更小的解？

定理 2
　　若 (a,n) = 1 及 a^d ≡ 1 (mod n) ， 則 d | Φ(n)

證：
　　假設定理不成立：
　　即，存在正整數 q 及 0 < r < d　使得 Φ(n) = qd + r
　⇒ a^{qd + r} ≡ 1 (mod n) -------(*)
　　另外，1^-1 ≡ 1 (mod n)
　⇒(a^d)^-1 ≡ 1 (mod n) -------(#)

　(#)^q × (*)：
　　a^r ≡ 1 (mod n)
　∴ a^d ≡ 1 (mod n) ⇒ a^r ≡ 1 (mod n) -------(!!!)

──重覆應用 (!!!) 將矛盾 Well Ordering Principle

---

算法 ── 總結：
由於 定理 2，我們可以枚舉 Φ(n) 的因數 f 搜尋答案：

其中最小而又滿足

　　a^f ≡ 1 (mod n) -------(6)

的 f 就是答案

---

算法 ── 實現及時複雜度：
如何計算 Φ(n) 及 枚舉 Φ(n) 的因數？

其實我們可以：
1) 計算 Φ(n) 的值 - O(sqrt(N))
[代碼後補...]
2) 枚舉 Φ(n) 的因素
　　枚舉 j := 0 to sqrt(Φ(n))
　　若 j | Φ(n)
　　　　分別代入 f := j 及 f := Φ(n) / j 入 (6) 測試

應用 Repeated Squaring，每個 Test case 的時間複雜度不超過 O( sqrt(N) lg(N) )

---

當然，我們可以用質因數連乘式了解決
不過這樣做比較麻煩...
現且上述算法已足夠快
在 PKU 上也只不過 94MS 而已...

---

P.S.: 今日Individual Training
我揀呢題既原因係... 之前見到唔識做, 想做左佢 XD