Create simple mvn project

1. mvn archetype:generate -DgroupId=com.mycompany.app -DartifactId=my-app -DarchetypeArtifactId=maven-archetype-quickstart -DinteractiveMode=false

2. mvn package

3. java -cp target/my-app-1.0-SNAPSHOT.jar com.mycompany.app.App

ProjectEuler #403

1. 條件 area of D(a, b) is a rational number 可以得到 relation between a and b。

2. 假設上面說的正確，L(a, b) 可以公式計算 ((不然也沒其他算法？不！還可以用猜的！))。

3. 假設上面說的正確，暴力法複雜度是 O(N^2) 恰巧可以利用 S(100) = 26709528 驗證演算法正確性，並且算出其他 S(某些數字)。

4. 假設題目滿足 ProjectEuler一分鐘定律，要能夠解決 N = 10^12，根據經驗，演算法複雜度有可能是：

• O(1)
• O(Log[N])，或者是 O((Log[N])^M) for some fix M，簡單說就是 Log[N] 多項式。 
• O(Sqrt[N])
• 其他比 O(N) 還要快的演算法。

這是心得。根據這樣子的心得，很容易找出目標演算法可能的複雜度（但離真正解開問題可能還有一段差距）

舉例來說：

(1) N = 10^7

演算法不能是 O(N^2)，但演算法複雜度會是 O(Sqrt[N]) 之類的嗎？恐怕不太可能，如果有如此演算法存在題目設計者就會把 N 調高一點，例如 N = 10^15。因此有可能是 O(N) 或是 O(N Log[N]^M) 之類的東西。

(2) N = 100

令人可疑的小數字，通常演算法差不多是 O(N^3) 到 O(N^4)，有可能有一些 Log[N] 多項式在裡頭。

(3) N = 10^10, 10^11

如果是 O(Sqrt[N]) 以下的演算法，感覺 N 可以在調高一點。所以判斷演算法差不多比 O(Sqrt[N]) 慢些但不會到 O(N)。

(4) N = 10^100, 10^10000

這種不合理的大數字，有可能把 N 當成無窮大使用（分析）。如果是求確實數字演算法很有可能是 O(1) 或者是 O(Log[N]^M) 之類的玩意兒。

Setup maven on mac

1. Download Apache Maven 3.3.1 (http://maven.apache.org/download.cgi)

2. Set environment variable

• export JAVA_HOME=$(/usr/libexec/java_home) 
• export PATH=$PATH:/Users/menggen/Downloads/apache-maven-3.3.1/bin 

3. Verify

• mvn --version

ProjectEuler #440

當初看錯題目，以為題目規定排出來的數字的 GCD 要等於 1，這樣根本沒辦法解下去。



做完發現沒有那麼困難，difficulty rating = 60%。然後前面還有兩題算超久：#152 跟 #185，兩大障礙，不過值得安慰的是 #185 可以利用題目來檢查答案對不對，不用傻傻輸入答案拿到一個紅紅的大叉叉。

全台灣鬼島第三名終於

解題分享



推薦大家看 Polya 寫的怎樣解題

• http://math.hawaii.edu/home/pdf/putnam/PolyaHowToSolveIt.pdf

Polya’s First Principle: Understand the problem

• 容易理解的題目，例如：https://projecteuler.net/problem=370
• 不太容易理解的題目，例如：https://projecteuler.net/problem=367

了解題目是很重要的第一步，如果連題目都看不懂或者是誤解題意可是很吃力的一件事。有些題目會給 small dataset，可以檢驗自己對於題目理解是否正確。



Polya’s Second Principle: Devise a plan

訂定解題計劃。

• Guess and check
• 數學靈感極佳的人可以嘗試
• Look for a pattern
• 我的愛招。
• 例子：https://projecteuler.net/problem=386。對於小數字情況利用有效率的演算法生出解答試圖找出規律。
• 很多題目知其然不知所以然的就這樣解決了。
• Make an orderly list
• Draw a picture
• 圖片提供直觀的論證
• 例子：https://projecteuler.net/problem=395
• Eliminate possibilities
• Solve a simpler problem
• 暴力法可以解決 small dataset，借此生成小數據測試資料。接著利用小數據測試資料提出有效率的演算法。
• 例子：https://projecteuler.net/problem=386。暴力法笨歸笨但還是有找出正確答案的能力（只是時間花很久而已）
• Use symmetry
• 計算數對個數常用伎倆。
• 特殊一點的用法有計算互質數對 (a, b)，接著再計算 (na, nb) 個數。
• Use a model
• 許多機率困難題目必須使用機率模型來處理，例如 Monte Carlo method，Markov chain
• Consider special cases
• Work backwards
• Use direct reasoning
• 直接坦過去。
• 例子：https://projecteuler.net/problem=218
• Use a formula
• 某些數論冷門題必須用冷門公式解答。
• 例子：https://projecteuler.net/problem=412
• Solve an equation
• 數論題目多屬於此類。有時候我們必須快速列舉畢氏三角形整數邊長，有時候我們必須計算 Totient Summatory Function 諸如此類。
• 例子：https://projecteuler.net/problem=446。直接沒有繞圈餘地。
• Be ingenious

Polya’s Third Principle: Carry out the plan

能夠紙筆計算的題目並不多，多數題目必須寫程式來縮短紙筆計算時間。熟悉並且熟練 C/C++/Java/Python 或是其他程式語言很重要。

實作上 C/C++ 必須留意常發生的 pointer/overflow 等問題。至於 Python 常犯的錯誤就是 list 沒有 deep copy。



Polya’s Fourth Principle: Look back

這點十分重要，解完題目一定要詳閱討論串。我看到許多人解完 ProjectEuler #1，用 O(n) 解完 ProjectEuler #1，便興匆匆貼上程式碼沒有仔細去看 O(1) 解法的妙味，ProjectEuler #1 不是獨立題目不是免洗筷解完就丟，後面許多題目都會利用規則性來快速計算個數（可能搭配排容原理或是有排容原理內含的定理），總之妙味無窮。

The Trinary Tree(s) underlying Primitive Pythagorean Triples

http://www.cut-the-knot.org/pythagoras/PT_matrix.shtml
http://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples

[FWD] HTTP 302

Thread Name:
Sample Start: 2014-09-05 12:01:16 CST
Load time: 64
Latency: 64
Size in bytes: 525
Headers size in bytes: 263
Body size in bytes: 262
Sample Count: 1
Error Count: 0
Response code: 302
Response message: Found

Response headers:
HTTP/1.1 302 Found
Cache-Control: private
Content-Type: text/html; charset=UTF-8
Location: http://www.google.com.tw/?gfe_rd=cr
Content-Length: 262
Date: Fri, 05 Sep 2014 04:01:17 GMT
Server: GFE/2.0
Alternate-Protocol: 80:quic


HTTPSampleResult fields:
ContentType: text/html; charset=UTF-8
DataEncoding: UTF-8

傳說中的 URL redirection，今天玩 jmeter 發現的。