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