Codeforces #132 (Div. 2) E - Periodical Numbers

Dynamic Scoring 是 3000 的題目 (所以也不是每個高手在現場解決了)
Virtual Participation 時花了 40 分鐘沒能搞定的題
不過當時有正確的大方向 (枚舉)

題意：

將一個正整數 X 表示為 n-bit 的 binary-string, S
不可以有前置零 (leading zeros)
若果存在 長度為 k < n 的 循環節 (period)
(i.e., 使得 S[i+k] = S[i]   for 0 <= i < n-k)
則稱 X 為 periodical

給定區間 [L, R], 問當中有多少個 periodical 的正整數

(題目連結)

思路：

先把問題簡化為
求 [1, R] 當中 periodical 正整數的個數

(那麼最後答案 := DOIT(R) - DOIT(L-1))

對於 循環節 長度為 k 的 X，可以將 X 表示成：

• X = Y × (00...01 00...01 00...01 ... 00...01)   (二進制表示及計算，下同)
• (00...01 00...01 00...01 ... 00...01) 是 m-bit 二進位數，其中 m <= n
• 每一個 00...01 是 k-bit 二進位數

[溫故知新,數論] Prmitive Root modulo n

(以下定義/定理或者未夠嚴僅... 數學人請見諒...)

記錄一下每年 "瞬耳即忘" 的數論知識...
雖然網上有很多 material
不過還是親手記下才更深刻
亦好讓日後能循著相似的思路重溫

先來的是在往年的 Training Record 就有提過...
而且(包括算法競賽)應用極廣的：

Theorem 1 (Euler's Totient Theorem)

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

---

Definition 1 (Multiplicative Order)

a 的 (multiplicative) order modulo n 是最小的 h
使得 a^h ≡ 1 (mod n)

以下為 (hopefully) 較直觀的解說：

a 的 order 就是 {x_i} 的最小循環節
其中 x₁ := 1 (mod m), x_k :=  x_k-1 × a (mod n)

---

Definition 2 (Primitive Root)

[舊帖] PKU 2480 Longge's problem

原文位置：http://www.xanga.com/private/editorx.aspx?uid=721833838

這是2010年度 CSC3270 的功課...

---

題意：

給定 N
計算 ∑_1≤i≤Ngcd(i, N)

---

算法：

Ans := 0
Foreach divisor of N, D
　　Ans += D × Phi( N / D )
EndFor

---

證明：

留意到 GCD(i, N) 必然是 N 的某個因數

ICPC 4270 Discret Square Roots

本星期 Individual Training 的題目
是 Hefei 2008 的題目

聲明：以下算法仍然有漏洞... 有待修補

---

題意：

給定 x, r, N
求出所有 y (1 ≤ y < N) 使得
y² = x (mod N)
其中已知
r² = x (mod N)

數據範圍：

• 2 ≤ N < 1,000,000,000
• 1 ≤ x, r < N

---

分析：

首先，你只有以下的公式：

y² = x (mod N) ──── (1)
r² = x (mod N) ──── (2)

(1) - (2) 得
(y-r)(y+r) = 0 (mod N)
⇒ (y-r)(y+r) = aN

2010-06-22 Individual Training

上星期二發現大家的 Number Theory 比較弱...
即使一些當中 Take 過 Number Theory 課的
似乎亦未能將知識比較皮毛的部份運用自如...

上星期四 Chin 講一下 Phi Function，Primitive Root 及 Discrete Logarithm 的一些應用及題目
再加上做過幾道題目以後：

• PKU 2417 Discrete Logging
• PKU 1284 Primitive Roots
• PKU 3696 The Luckiest number
  

貌似終於對這類課題（尤其是 Phi Function）比較有感覺

所以... 在今天的個人Training 特意挑了 (比較多) Number Theory 的題目，大家一起做
不過... 呃... 感覺大家做的時候比較絕望，所以更加要練習！

---

Problem A: PKU 3766 Hexagon Coin Toss
問：給定一些類似下圖所示，由邊長為 1 的正六邊形組成的 "M x N" 棋盤。現有一單位圓（直徑 < 1）隨機出現，其圓心必定在棋盤內，求該圓覆蓋 1, 2, 3 格的概率

解：畫圖直接分析... 可以參考 Roba 的 blog

Problem B: PKU 1061 青蛙的约会
問：求最小的 x 使得 vx = d (mod n)
解：擴展歐基里德算法（Extended Euclidean Algorithm）

Problem C: PKU 3358 Period of an Infinite Binary Expansion
問：求當 a/b 表示為2進制時，最短循環節的長度，及循環開始的位置
解：Phi Function。推導出來的式子跟 PKU 3696 The Luckiest number 那時幾乎一樣，可以參考 舊文... (有時間再寫一下推導過程...)
按1：所有情況下，即使是 1/8，循環節依然 ≥ 1！
按2：呃... 這道題在 ICPC Live Archive 上面也有，不過數據很水。今次 Training 沒選 PKU 的，然後不少人以 O(答案) 的算法水過，失去了某些意義... ~_~

Problem D: UVa 10692 Huge Mod
問：給個例子說明吧...
　　
在 mod 左邊的數字值 ≤ 10000，最多 10 個
解：呃... 還未做，不過大概是統計形如 {aⁱ mod N} 的循環節長度。（鴿巢原理 ⇒ 循環節長度 ≤ 10000 ⇒ 可枚舉）實現涉及 Recursion，感覺比較噁心...

Problem E: PKU 1997 Word Puzzle
問：題目有點長... 自己看吧
解：以 Trie 記錄 pattern。對表格每個位置，分別朝上下左右 etc八個方位掃描，檢查能否找到 任何 pattern。
Joe 說能用 AC自動機 加快，但本人對這東西不了解

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)

---

以下為最關鍵的一步！