USACO 2012 三月 金組

第一題：

關鍵：

這個數量約等於 nlgn，因為你在建表的時候，大致像下面那樣

for(int i = 1; i < N; i++)
        for(int j = i; j < N; j += i) P[j].PB(i); 

這樣子的數量級差不多是O(nlgn)，因為 sum of 1/x 是 lgn。

所以：2^質因數個數 <= 因數的數量 <= nlgn

至於第一項是哪裡來的呢？是排容原理。

總之因數數量的總和其實是很小的，要注意這一個地方。

第二題：

相信大家都寫過，這題直鏈的版本，想通就解決了，較為簡單的一個題目。

第三題：

       我寫的是一個暴力搜的方法，並用目前答案去做剪枝，但這種作法在暴力方式是1*2*3*4*5*6*7...這樣子會比較有效。

       我一開始寫的暴力方式 n*n-1*n-2...，就會顯得沒有什麼意義，以後要多想由小到大的方法，會比較好Cut。

      官方題解不知道是在寫什麼毛，明天再去看看。