real

2011年7月26日星期二

[溫故知新,數論] 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)

2011年7月1日星期五

隨筆 2011-07-01 - Finals 過後...

不是考試的 Finals...
是 ACM World Finals...

World Finals 戰記一直沒心情寫
因為太遺憾吧...
(話說當日正賽過後回到房間我居然哭了... 都多少年沒有事情讓我哭過了...)

在 Joe 發佈戰記那一天
才有一點刺激讓我花幾個小時一口氣寫了一大堆...
不過那才記述了三份一至二份之一...
然後又因沒心情 +種種事務繁忙一直沒有再寫...

就這樣, 居然一拖便拖了一個月時間...

今年是 CUHK 的尖峰吧...?