定義一個正整數(shù)n的函數(shù)F(n)為n的每位數(shù)的乘積。一個數(shù)是good如果F(n)不為0并且n能整除F(n)，一個數(shù)是完美數(shù)當且僅當n是good并且n+1也是good。現(xiàn)在問一個長度是k位的數(shù)中有多少個完美數(shù)，其中k不大于1000000。
　　不得不承認這是一個非常經(jīng)典的鍛煉分析問題能力的題目。設(shè)n = a1a2...an，因為F(n)不為0，所以n + 1 = a1a2...(an+1)。根據(jù)題目意思，我們可以列出等式：n + 1 = q * (a1 * a2 * ... * (an + 1))，又n = p * (a1 * a2 * ... * an)。令A(yù) = a1 * a2 ... * an-1，整理前面的等式可以得到：(q * an + q - an) * A = 1。因為這里面都是整數(shù)，顯然A = 1，也就是說a1，a2，...，an-1都是1。問題一下子就變得簡化了很多，比起之前的單純枚舉可以說是進了一大步。但是如果枚舉最后一位判斷是不是可行復(fù)雜度依然很高，需要進一步討論。首先an是1、2、5對應(yīng)的數(shù)都是good；an為3的時候，如果是good必須前面n-1個1加和是3的倍數(shù)；an為4的時候需要最后兩位被4整除才行，14不滿足條件；同理an為6的時候也必須前面n-1個1加和是3的倍數(shù)；an為8的時候需要后三位的數(shù)被8整除，顯然也不可能；經(jīng)過一番討論，就剩7這個特別的數(shù)字了。用一堆1對7試除一下發(fā)現(xiàn)一個規(guī)律，111111恰好整除7，六個數(shù)一循環(huán)。這樣只需判斷(an - 1)是否整除6就可以了。
　　綜上所述，對于一個k位的數(shù)字，如果k為1，那么結(jié)果是8。如果k大于1，結(jié)果首先是1，如果k-1能被3整除，結(jié)果加2；如果k-1能被6整除，結(jié)果再加1。這樣O(1)的時間復(fù)雜度就出結(jié)果了，仔細分析問題后得出的做法真強大啊。