大整數的快速質因子分解，用到pollard-rho啟發式算法。
　　算法導論上介紹pollard-rho介紹得比較詳細，由于小因子的循環節長度很小，通過倍增步長，pollard-rho能夠很快的找到一個大整數的一個較小的素因子p，書中說復雜度在O(sqrt(p))內，用的什么概率的分析方法，不懂。實際中pollard-rho的速度還是很快的，當然可能出現死循環。
　　這個題目要利用pollard-rho找到一個數的最小素因子，因此還需要Miller-Rabin測試來輔助。原來寫的那個Miller-Rabin很快掛掉了，因為沒有用到二次探測，判不出來Carmichael數。如果x ^ 2 = 1 (mod n)，如果n是質數，那么x只能是1和n - 1；二次探測就是利用這個定理來進行檢測。
　　POJ的論壇里面更有牛人列出了N多Carmichael數，真不知道他怎么找到的。最初怎么也不知道二次探測加在哪里好，后來參考網上一位大牛的代碼，它的方法是計算a ^ b % n的時候，先將b折半到一個奇數b'為止，計算a ^ b'，然后倍增b'，同時進行二次檢測，想想覺得很有道理，因為如果x ^ 2 = 1 mod n成立的話，那么(x ^ 2) ^ 2 = 1 mod n也成立。
　　這個題目還有一個trick就是模能達到2 ^ 54，如果這樣計算一個數平方的時候，即使long long也會溢出。后來發現可以用快速冪取模的思想弄個"快速積取模"，同樣將b表示成二進制的形式，倍增的同時加到結果上就行了。這樣每次運算的數范圍都在2 ^ 54以內，并且都是加操作，不會溢出了。
　　POJ上還有一個用pollard-rho做的題是PKU 2429，這個比Prime Test還惡，因為這個題目是徹徹底底進行factorization，而且之后還要枚舉一下找最優解，總之我的代碼非常的長，而且這個題目數據范圍2 ^ 63，必須用unsigned long long才能過。我的代碼中間出現了一些減操作，都要特殊處理一下。最后還犯了個低級錯誤，函數返回值寫錯了，找了好幾遍才找出來。

附PKU 1811代碼：

題目大意是給定一個數n，問約數個數為n的最小的數k是多少。其中1 <= n <= 10000, k <= 10 ^ 15。
這是一個經典問題了，我一直以為會有經典算法，開始的時候一直往貪心上想，結果owen給出了反例。后來經過吉大牛點撥，因為k <= 10 ^ 15，可以根據這個定界，最差情況k的素因子也不會超過13，這樣就可以搜索了！
實現的時候我也犯了幾個小錯，一個是把10 ^ 15少打了一個0，還有一個剪枝必須加：如果當前結果的約數個數為f，那么如果n % f不為0，則剪掉，因為約數個數是以乘積的關系累加的。
　　給定一個數N（N <= 10 ^ 1000），如何快速求得N！的最末位非零數是一個經典的問題。一直以來都被這個問題困擾，今天仔細想了下，終于給想通了，盡管可能有些笨拙，現把想法記錄于此。
　　在N很小的情況下，有一個簡便的方法：求出1到N之間每個數的2的因子數和5的因子數，記為F(2)和F(5)，顯然F(2) >= F(5)。由于在末尾只有2和5相乘才能產生0，如果我們把2和5拋去，那么肯定不會有0，這樣就可以一邊乘一邊模10，防止溢出。剩下的一堆2和5如何處理呢？因為2肯定比5多，因此最末位肯定是偶數（0的階乘和1的階乘除外）。而一個偶數不停地乘2，最末位的規律是：2 -> 4 -> 8 -> 6 -> 2 -> ...出現了4位1循環，這樣我們先用F(2) - F(5)，使得一部分2和5匹配上，2 * 5 = 10，對末尾不產生影響，剩下的2就模一下4，剩幾再乘幾次2就可以了。
　　但是這個方法在N非常大的時候肯定就不行了，但是可以利用找循環這個思想繼續做。如果算階乘的時候跳過5的倍數，記G(n)為跳過5的倍數的時候，從1乘到n的最末非零位，也就是把5的倍數當1乘?？梢园l現：
G(1) = 1, G(2) = 2, G(3) = 6, G(4) = 4, G(5) = 4, G(6) = 4, G(7) = 8, G(8) = 4, G(9) = 6, G(10) = 6, G(11) = 6, G(12) = 2, G(13) = 6...
　　又出現了循環，每10個數循環一次。如何計算G(n)就變的很簡單，求出n的最末位，就知道對應的G(n)是多少了，當然需要特判n = 1的情況。由于我們把5的倍數的數都提出來了，提出來的這些數（5、10、15、20、25、30...）每個除以5后又組成了一個階乘序列！除完5一共提出了n / 5個5，根據之前的分析，每個5都可以拿出一個2和它配對然后把它消去，這樣一個5就相當于少一個2，我們就要把原來的數乘以3個2（模四循環）。這樣一來5的個數其實也可以模四，模完四之后剩k的話，就可以乘以k個8，就把所有的5消去了?，F在總結一下：對一個數n的階乘，計算它的末尾非零位，先計算G(n)，相當于非5的倍數的數的乘積最末非零位先算好了，然后乘以n / 5 % 4個8，處理了提出的n / 5個5，這樣之后還剩下n / 5的階乘沒有算。遞歸的求解n / 5的階乘的最末位非零數，再乘上去就得到結果了。
　　這個做法的復雜度就很低了，達到O(log n)，對于10 ^ 1000的數據，利用高精度做就行了。利用這種循環的思想，算排列數P(n, k)的最末非零數也就可以做到了。
附HOJ 1013代碼：
     摘要: 一道思路很簡單的計算幾何題目，就是先判是不是“凸多邊形”，然后計算點到直線的最短距離。但是我錯了很多次。一個問題就是有可能peg不在多邊形內，這要單獨判斷一下；還有一個問題找了很久才發現，原來題目中說滿足條件的多邊形不是純粹的凸多邊形，題目中的多邊形是“任意內部兩點連線不會和多邊形的邊相交”，這樣如果多邊形的多個頂點存在共線的情況，其實也是可以的，但...  閱讀全文

最近又研究了線性篩素數方法的擴展，的確非常強大。
經典的應用是線性時間篩歐拉函數和求約數個數。我想了一下線性時間篩約數和(積性函數)，也是可行的。
對于一個大于1的數n，可以寫成p1 ^ a1 * p2 ^ a2 * ... * pn ^ an，那么n的約數和就是(p1 ^ 0 + p1 ^ 1 + ... p1 ^ a1) * ... * (pn ^ 0 + ... + pn ^ an)，由此就可以有遞推關系了：
設f[i]表示i的約數和，e[i]表示i的最小素因子個數，t[i]表示(p1 ^ 0 + .. + p1 ^ a1)，p1是t的最小素因子，a1是p1的冪次，這樣對于i * p[j]，如果p[j]不是i的因子，那么根據積性條件，f[i*p[j]] = f[i] * (1 + p[j])，e[i] = 1，t[i] = 1 + p[j]；如果p[j]是i的因子，那么相當于t[i]多了一項p1 ^ (a1 + 1)，首先e[i]++，然后tmp = t[i]，t[i] += p[j] ^ e[i]，f[i*p[j]] = f[i] / tmp * t[i]。這樣也就做到了O(1)的時間計算出了f[i*p[j]]同時也計算出了附加信息。

這種方法還可以繼續推廣，例如可以記錄i的最小素因子，這樣就可以做到O(log n)時間的素因子分解。