Problem 324 Factorial Frequencies，階乘的數字頻率

這題要先計算小於等於366的階乘，然後再算出答案中各個數字出現的頻率。因為366!的解答位數有781個，因此乘積必須另外處理，我使用一個782大小的short陣列，下列是處理一次相乘的運算過程，digitNum是目前乘積的位數，quotient是乘數，m是被乘數，因為m <= 366，所以只需要一個大小為四的陣列暫放單次乘積，所有乘積的再加總到 tempQuotient，最後再將tempQuotient 取代 quotient。

    for (i=0;i<digitNum;i++)
    {
        temp = m * quotient[i];
        tempSingleQuotient[0] = temp%10;
        tempSingleQuotient[1] = (temp/10)%10;
        tempSingleQuotient[2] = (temp/100)%10;
        tempSingleQuotient[3] = temp/1000;
        addOn = 0;
        for (j=i;j<i+4;j++)
        {
            tempQuotient[j] += tempSingleQuotient[j-i] + addOn;
            if (tempQuotient[j]>9)
            {
                tempQuotient[j] %= 10;
                addOn = 1;
            }
            else
                addOn = 0;
        }
        if (addOn==1)
            tempQuotient[j]++;
    }

366!的答案參考如下：

91881110952544960192121764120652021400905804187746451946753698409678048465888630
95597762591294093025991679067056119532289819154031153412626361004655299317292397
49179412498318319018148586317535633967317457727070935401134984115987016231538802
10775515745441503394546772632592927414904702786529187586181553191933821765407560
99231912808304474174078456156193961001478398647954868692612278257154615836148475
87497304417332305563008204883785367990054205910511284539407194719244320847853070
01945328184598553156206617049504666959657009975517485204759412277436981211121307
99760005290512978278155471280205501581277410145813062661991385483143379923345195
40643216551834035171686893165020312665044431520399360000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000

輸出結果為：

366! --
   (0)  160    (1)   93    (2)   58    (3)   60    (4)   74
   (5)   81    (6)   58    (7)   64    (8)   59    (9)   74

p324題目連結
回ACM題庫目錄
回首頁