作者：上善若水、July、yansha。
出處：http://blog.csdn.net/v_JULY_v 。
前奏
本章陸續(xù)開(kāi)始，除了繼續(xù)保持原有的字符串、數(shù)組等面試題之外，會(huì)有意識(shí)的間斷性節(jié)選一些有關(guān)數(shù)字趣味小而巧的面試題目，重在突出思路的“巧”，和“妙”。本章親和數(shù)問(wèn)題之關(guān)鍵字，“500萬(wàn)”，“線性復(fù)雜度”。
第一節(jié)、親和數(shù)問(wèn)題
題目描述：
求500萬(wàn)以內(nèi)的所有親和數(shù)
如果兩個(gè)數(shù)a和b，a的所有真因數(shù)之和等于b,b的所有真因數(shù)之和等于a,則稱a,b是一對(duì)親和數(shù)。
例如220和284，1184和1210，2620和2924。
分析：
首先得明確到底是什么是親和數(shù)?
親和數(shù)問(wèn)題最早是由畢達(dá)哥拉斯學(xué)派發(fā)現(xiàn)和研究的。他們?cè)谘芯繑?shù)字的規(guī)律的時(shí)候發(fā)現(xiàn)有以下性質(zhì)特點(diǎn)的兩個(gè)數(shù)：
220的真因子是：1、2、4、5、10、11、20、22、44、55、110；
284的真因子是：1、2、4、71、142。
而這兩個(gè)數(shù)恰恰等于對(duì)方的真因子各自加起來(lái)的和（sum[i]表示數(shù)i 的各個(gè)真因子的和），即
220=1+2+4+71+142=sum[284],
284=1+2+4+5+10+11+20+22+44+55+110=sum[220]。
得284的真因子之和sum[284]=220，且220的真因子之和sum[220]=284，即有sum[220]=sum[sum[284]]=284。
如此，是否已看出絲毫端倪?
如上所示，考慮到1是每個(gè)整數(shù)的因子，把出去整數(shù)本身之外的所有因子叫做這個(gè)數(shù)的“真因子”。如果兩個(gè)整數(shù)，其中每一個(gè)真因子的和都恰好等于另一個(gè)數(shù)，那么這兩個(gè)數(shù)，就構(gòu)成一對(duì)“親和數(shù)”（有關(guān)親和數(shù)的更多討論，可參考這：http://t.cn/hesH09）。
求解：
了解了什么是親和數(shù)，接下來(lái)咱們一步一步來(lái)解決上面提出的問(wèn)題（以下內(nèi)容大部引自水的原話，同時(shí)水哥有一句原話，“在你真正弄弄懂這個(gè)范例之前，你不配說(shuō)你懂?dāng)?shù)據(jù)結(jié)構(gòu)和算法”）。
- 看到這個(gè)問(wèn)題后，第一想法是什么？模擬搜索+剪枝？回溯？時(shí)間復(fù)雜度有多大？其中bn為an的偽親和數(shù)，即bn是an的真因數(shù)之和大約是多少？至少是10^13（@iicup：N^1.5 對(duì)于5*10^6 , 次數(shù)大致 10^10 而不是 10^13.）的數(shù)量級(jí)的。那么對(duì)于每秒千萬(wàn)次運(yùn)算的計(jì)算機(jī)來(lái)說(shuō)，大概在1000多天也就是3年內(nèi)就可以搞定了（iicup的計(jì)算: 10^13 / 10^7 =1000000(秒) 大約 278 小時(shí). ）。如果是基于這個(gè)基數(shù)在優(yōu)化，你無(wú)法在一天內(nèi)得到結(jié)果的。
- 一個(gè)不錯(cuò)的算法應(yīng)該在半小時(shí)之內(nèi)搞定這個(gè)問(wèn)題，當(dāng)然這樣的算法有很多。節(jié)約時(shí)間的做法是可以生成伴隨數(shù)組，也就是空間換時(shí)間，但是那樣，空間代價(jià)太大，因?yàn)閿?shù)據(jù)規(guī)模龐大。
- 在稍后的算法中，依然使用的伴隨數(shù)組，只不過(guò)，因?yàn)轭}目的特殊性，只是它方便和巧妙地利用了下標(biāo)作為伴隨數(shù)組，來(lái)節(jié)約時(shí)間。同時(shí)，將回溯的思想換成遞推的思想（預(yù)處理數(shù)組的時(shí)間復(fù)雜度為logN（調(diào)和級(jí)數(shù)）*N，掃描數(shù)組的時(shí)間復(fù)雜度為線性O(shè)（N）。所以，總的時(shí)間復(fù)雜度為O（N*logN+N）（其中l(wèi)ogN為調(diào)和級(jí)數(shù)） ）。
第二節(jié)、伴隨數(shù)組線性遍歷
依據(jù)上文中的第3點(diǎn)思路，編寫如下代碼：
int sum[5000010]; //為防越界
int main()
{
int i, j;
for (i = 0; i <= 5000000; i++)
sum[i] = 1; //1是所有數(shù)的真因數(shù)所以全部置1
for (i = 2; i + i <= 5000000; i++)
{
//5000000以下最大的真因數(shù)是不超過(guò)它的一半的
j = i + i; //因?yàn)檎嬉驍?shù)，所以不能算本身，所以從它的2倍開(kāi)始
while (j <= 5000000)
{
//將所有i的倍數(shù)的位置上加i
sum[j] += i;
j += i;
}
}
for (i = 220; i <= 5000000; i++) //掃描，O（N）。
{
// 一次遍歷，因?yàn)橹雷钚∈?20和284因此從220開(kāi)始
if (sum[i] > i && sum[i] <= 5000000 && sum[sum[i]] == i)
{
//去重，不越界，滿足親和
printf("%d %d/n",i,sum[i]);
}
}
return 0;
}
第三節(jié)、程序的構(gòu)造與解釋
我再來(lái)具體解釋下上述程序的原理，ok，舉個(gè)例子，假設(shè)是求10以內(nèi)的親和數(shù)，求解步驟如下：
因?yàn)樗袛?shù)的真因數(shù)都包含1，所以，先在各個(gè)數(shù)的下方全部置1
- 然后取i=2,3,4,5（i<=10/2），j依次對(duì)應(yīng)的位置為j=（4、6、8、10），（6、9）,（8）,（10）各數(shù)所對(duì)應(yīng)的位置。
- 依據(jù)j所找到的位置，在j所指的各個(gè)數(shù)的下面加上各個(gè)真因子i（i=2、3、4、5）。
整個(gè)過(guò)程，即如下圖所示（如sum[6]=1+2+3=6，sum[10]=1+2+5=8.）：
1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1
2 2 2 2
3 3
4
5 - 然后一次遍歷i從220開(kāi)始到5000000，i每遍歷一個(gè)數(shù)后，
將i對(duì)應(yīng)的數(shù)下面的各個(gè)真因子加起來(lái)得到一個(gè)和sum[i]，如果這個(gè)和sum[i]==某個(gè)i’，且sum[i‘]=i，
那么這兩個(gè)數(shù)i和i’，即為一對(duì)親和數(shù)。 - i=2；sum[4]+=2，sum[6]+=2，sum[8]+=2，sum[10]+=2，sum[12]+=2...
i=3，sum[6]+=3，sum[9]+=3...
...... - i=220時(shí)，sum[220]=284，i=284時(shí)，sum[284]=220；即sum[220]=sum[sum[284]]=284，
得出220與284是一對(duì)親和數(shù)。所以，最終輸出220、284，...