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) 之類的玩意兒。