[溫故知新,數論] 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-07-01 - Finals 過後...

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

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

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

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

---

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

[ACM ICPC] World Finals 2011 : Day 2 熱身

(近兩日上網速度大覆降低...)
(相片後補...)

是日活動全部在酒店舉行
但行程相當緊湊

---

Opening Ceremony
跟以往差不多

---

Contest Orientation
試了 stack size 等等的東西
貌似拿了個還可以的 rank 3

[ACM ICPC] World Finals 2011 : Day 1 SeaWorld Orlando※Welcoming

天氣仍是極好

IBM tech talk @ SeaWorld      @@
Whale show



看了各種海洋生物
拍了頗多 相片 / 影片

雲宵飛車 : Manta, Kraken 非常恐怖

[ACM ICPC] World Finals 2011 : Day 0 Training※Florida Mall※Registration

早上 7:30am

---

今天的早餐是 Omelet
很貴........

---

9am~2pm - Training: Pacific Northwest 2010
有點不順利
大量TLE (雖然很懷疑 on site 時間應該更加寛鬆)

嗯... 這次應該是人生中最後一次ACM Training...
ACM 生涯快要結束了...
稍有感觸...

[ACM ICPC] World Finals 2011 : Day -1 Training※Disneyland

Slept at 12am, woke up at 7:30am...

Training : 9am~1:30pm - World Finals 2007

A bit tired... maybe jet lag
but seems that a coffee is a must for waking me up early in the morning...

[ACM ICPC] World Finals 2011 : Day -2 抵步

雖然在香港出發前出現一些波折遲了點登機
但最後我們以及所有行李總算平抵抵步

花了大約24小時
終於到達酒店... Peabody@Orlando

---

我們的行程是這樣的：

• Hong Kong → Chicago (~14.5 HR)
• 等候轉機 (~4 HR)
• Chicago → Orlando (~3 HR)
• Immigration + Taxi to hotel (~1 HR)

(略過某些等候的時間)

隨筆 2011-05-20

相信自己
相信隊友

---

Time to World Final: 9 days, 15 hours, 52 minutes, 24 seconds

SRM 504.5 Live

900 - 將 1/3 跟 1/2 弄反了
最後十分鐘才發現
隨即通過sample
然後最後幾分鐘才發現我的算法是 O(N^3), TLE
(估計 n>=500 可以approximate ?)

- 完

隨筆 2011-05-04

術式：嘈音攻擊
效果：目標各項能力值下降 70%、憤怒值上昇 50%

Hefei 2009 Problem H - Chinese Paper Cutting

Hefei 2009 Problem H AC 留念...
LOC ~= 280

---

題目大意（嚴謹細節略去）：
給一長方形紙張，T 個操作，操作分兩種：

1. 垂直／打橫對摺
2. 沿著某些連續的水平／垂直線段栽剪

在每個栽剪操作後，若果紙張被分為多個部份，只保留面積最大的部份。
在所有操作完成後，還原所有對摺操作。

求最終剩餘的紙張部份。

2011-03-23 Team Training - World Finals 2004

2011-03-23 Wed
HKG Time - 1900 to 2400

啱啱尋晚係 research deadline 後
第二次正式齊腳 training

今次做 World Finals 2004
悲劇呀！

• 題目 (Live Archive)
• Scoreboard

SRM 500 - Live

500大賽...
很難的一SET題目

250 我花了 45+ 分鐘才通過 sample...
不過縱使通過 sample 也不代表甚麼...
預期會有大量 fail system test 出現...
對自己的 submission 也沒有大期望...........

其後我看了 500
長方形的四個角落是整數座標
所以，我想大概算法是先預處理每一個格子
[x, x+1) × [y, y+1)
所包括的線段總長度吧
DFS 就好了，深度大約去到第六層
有想法，式子也準備好
但沒有足夠時間實現，更別說測試了...

但感覺 500 若能通過 sample
比起 250，應該有更大機會通過 system test

Petr 等一眾高手完成了全部 3 題...

---

rng_58 單做 1000 Rank 6th

Judge 完了
250 通過了
Rank 4th in room → 沒錢分 sosad

---

甚麼?!
lucky draw 中獎了-.-

[2D Geomtry] 二維線段交點

在本篇 entry 我們談一談二維線段交點求解方法
本人認為，最後討論的 "三角形面積方法" 的解相當優美

---

直線方程組方法

中學時期，我們都學過用聯立方程組求 線 / 線交點：

A x + B y = C
D x + E y = F

可這個方法缺點是
用代入法 (substitution) 或消元法  (elimination) 求出的一般解
在 x系數 = 0 或 y系數 = 0 的情況需要特別分開處理

我們亦不能單從 solution
簡單判斷交點 Q 是否在線段 AB 或 CD 之內

---

向量方法

這是在 year 1 暑假 ACM training 時學會的
感覺相當強大、漂亮

將兩條線段表示成：

P₁ = A + s AB -------- (1)
P₂ = C + t CD -------- (2)

其中 s, t 分別是 線段AB,CD 的參數

SRM 498 - Live

So many familiar handles in my room...
This time 250 and 450 are very easy, but I solved them so slowly... :(

隨筆 2011-02-17 - 亂七八糟的寫一篇...

有時候真的發覺「成事在天」

Paper的事... 也由不得我擔心太多

---

先前 Conference paper deadline 跟 ICPC World Finals 撞期了
後來 World Finals 又因為埃及政治事件需要延期...

在我來看，算是好事

[UVa] Sixth Contest of Newbies

Links：

• 賽事題目 / Scoreboard
• UVa OJ 題目 (UVa 11909~11914)

余以為絕對是值得花時間做的一SET題目...

題目質素高
時限相當緊
Test Data 亦相當狠 (很多 set...)
(題目也相當 "陰"...)

雖然具備基本知識，理論上新手都可以解出起碼三題
不過... 這都包含相當多細節，不是一般的題目呀...

---

題解概要：

A: Soya Milk - 簡單2D幾何
分兩種情況：水平線 touch length/height

B: Closest Fractions - 枚舉
Contest 時 RP較高
預處理GCD後 O(1000^2) 暴試 0.9xx sec 水過了

SRM 495

藍色留念...

http://www.topcoder.com/stat?c=round_overview&er=5&rd=14424

Codeforces #57

2010-02-26 Wed
HKG Time - 0000 to 0200

終於... 在一次 individual contest 做到少人完成的難題目了...!

• 題目
• 排名 (12th)
• 官方 Analysis

---

題解概要：

HDU 3748 Equivalent mass

Problem Statement:

• Given N elements, A[N], determine if it is possible to pick exactly K of them s.t. the sum is V. But you cannot pick X^th and Y^th simultaneously, for some given pairs (X, Y). There are M such pairs.

Constraints:

• 1 <= N <= 32
• 1 <= A[i], V <= 10^9
• 0 <= M <= 6
• 0 <= K <= N