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

附PKU 1811代碼：

PKU 1811
  1 #include <cstdio>
  2 #include <stdlib.h>
  3 #include <time.h>
  4 const int MAX = 8, N = 1000010;
  5 
  6 long long ans, p[N/5];
  7 int tag[N];
  8 
  9 long long abs(long long t)
 10 {
 11     return t < 0 ? -t : t;
 12 }
 13 void prime()
 14 {
 15     int cnt = 0;
 16 
 17     for (int i = 2; i < N; i++)
 18     {
 19         if (!tag[i])    p[cnt++] = i;
 20         for (int j = 0; j < cnt && p[j] * i < N; j++)
 21         {
 22             tag[i*p[j]] = p[j];
 23             if (i % p[j] == 0)
 24                 break;
 25         }
 26     }
 27 }
 28 long long gcd(long long a, long long b)
 29 {
 30     return !b ? a : gcd(b, a % b);
 31 }
 32 long long MultiMod(long long a, long long b, long long k)
 33 {
 34     long long ret = 0, tmp = a % k;
 35 
 36     while (b)
 37     {
 38         if (b & 1)
 39             ret = (ret + tmp) % k;
 40         tmp = (tmp << 1) % k;
 41         b >>= 1;
 42     }
 43 
 44     return ret;
 45 }
 46 long long PowerMod(long long a, long long b, long long k)
 47 {
 48     long long ret = 1, f = a % k;
 49 
 50     while (b)
 51     {
 52         if (b & 1)
 53             ret = MultiMod(ret, f, k);
 54         f = MultiMod(f, f, k);
 55         b >>= 1;
 56     }
 57     return ret;
 58 }
 59 int TwiceDetect(long long a, long long b, long long k)
 60 {
 61     int t = 0;
 62     long long x, y;
 63 
 64     while ((b & 1) == 0)
 65     {
 66         b >>= 1;
 67         t++;
 68     }
 69     y = x = PowerMod(a, b, k);
 70     while (t--)
 71     {
 72         y = MultiMod(x, x, k);
 73         if (y == 1 && x != 1 && x != k - 1)
 74             return 0;
 75         x = y;
 76     }
 77     return y != 1 ? 0 : 1;
 78 }
 79 bool MillerRabin(long long n)
 80 {
 81     int i;
 82     long long tmp;
 83 
 84     srand(time(0));
 85     for (i = 0; i < MAX; i++)
 86     {
 87         tmp = rand() % (n - 1) + 1;
 88         if (TwiceDetect(tmp, n - 1, n) != 1)
 89             break;
 90     }
 91     return (i == MAX);
 92 }
 93 long long pollard_rho(long long n)
 94 {
 95     srand(time(0));
 96     int i = 1, k = 2;
 97     long long d, x = rand() % (n - 1) + 1, y = x;
 98     while (true)
 99     {
100         i++;
101         x = (MultiMod(x, x, n) - 1) % n;
102         d = abs(gcd(y - x, n));
103         if (d != 1 && d != n)
104             return d;
105         if (i == k)
106         {
107             y = x;
108             k <<= 1;
109         }
110     }
111 }
112 void factorization(long long n)
113 {
114     long long tmp;
115 
116     if (n < N)
117     {
118         ans <?= !tag[n] ? n : tag[n];
119         return;
120     }
121     if (MillerRabin(n))
122     {
123         ans <?= n;
124         return;
125     }
126     tmp = pollard_rho(n);
127     factorization(tmp);
128     factorization(n / tmp);
129 }
130 
131 int main()
132 {
133     int T;
134     long long n;
135 
136     scanf("%d", &T);
137     prime();
138     while (T--)
139     {
140         scanf("%I64d", &n);
141         if (n < N)
142         {
143             if (tag[n] == 0)
144                 puts("Prime");
145             else
146                 printf("%d\n", tag[n]);
147             continue;
148         }
149         if (MillerRabin(n))
150             puts("Prime");
151         else
152         {
153             ans = 0xfffffffffffffffLL;
154             factorization(n);
155             printf("%I64d\n", ans);
156         }
157     }
158 
159     return 0;
160 }
161