PKU 1454-Factorial Frequencies

PKU

問題概要

N!に含まれる0から9までの各数字の個数を求めよ

解法

多倍長で計算して，文字列に直して数える．

実装(C++)

deque多倍長

#include <deque>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;
const int BI_MAX=10000;
struct BigInteger{
        deque<short> val;
        BigInteger(int n=0){
                while(n)val.push_back(n%BI_MAX),n/=BI_MAX;
        }
        void clear_leading_zero(){while(val.back()==0)val.pop_back();}
        string to_string(){
                if(val.size()==0)return "0";
                char res[val.size()*4+5];char *r;r=res+val.size()*4+4;*(r--)='\0';
                for(int i=0;i<(int)val.size();i++){
                        int t=val[i];
                        for(int j=0;j<4;j++){
                                if(t==0&&i==(int)val.size()-1)break;
                                (*r--)=t%10+'0';
                                t/=10;
                        }
                }
                return string(r+1);
        }
};
BigInteger mul(const BigInteger &a,const BigInteger &b){
        int k=0,i,j;
        BigInteger res(0);
        for(int i=0;i<(int)a.val.size()+(int)b.val.size()+1;i++){
                res.val.push_back(0);
        }
        for(i=0;i<(int)a.val.size();i++){
                k=0;
                for(j=0;j<(int)b.val.size();j++){

                        k=a.val[i]*b.val[j]+k;
                        res.val[i+j]+=k%BI_MAX;
                        k/=BI_MAX;
                        if(res.val[i+j]>=BI_MAX){
                                res.val[i+j]-=BI_MAX;k++;
                        }
                }
                while(k){
                        res.val[i+j]+=k;
                        if(res.val[i+j]>=BI_MAX){res.val[i+j]-=BI_MAX;k=1;}else k=0;
                        j++;
                }
        }
        res.clear_leading_zero();
        return res;
}
BigInteger operator*(const BigInteger &a,const BigInteger &b){return mul(a,b);}
BigInteger Fact[367];
int main() {
	Fact[0]=1;
	for(int i=1;i<367;i++)Fact[i]=Fact[i-1]*i;
	for(int n;scanf("%d",&n),n;){
		int f[10];
		fill(f,f+10,0);
		string t=Fact[n].to_string();
		int L=t.size();
		for(int j=0;j<L;j++){
			f[t[j]-'0']++;
		}
		printf("%d! --\n",n);
		printf("   (0)%5d    (1)%5d    (2)%5d    (3)%5d    (4)%5d\n",f[0],f[1],f[2],f[3],f[4]);
		printf("   (5)%5d    (6)%5d    (7)%5d    (8)%5d    (9)%5d\n",f[5],f[6],f[7],f[8],f[9]);
	}
	return 0;
}