UVA - 10061 How many zero's and how many digits

UVA - 10061 How many zero's and how many digits ?

这道题分为两个部分：

（1）求N！在B进制下末尾0的个数。若有K个0，则N！可表示为X*B^K，X为末位不为0的正整数。

不能分别求从2到N对应的K值然后求和，例如N=5，B=10中，2到5对应的K值均为0：2=2*10^0，……5=5*10^0，但5！=120对应的K值为1：120=12*10^1。

换一个角度，比较因子的阶数。若B=∏Ai^Bi，N！=X*∏Ai^Ci，又因为N！= X*B^K= X*（∏Ai^Bi）^K= X*∏Ai^（Bi*K），则K=min（Ci/Bi）。

Ci 的求法：若Ni=Xi*∏Ai^Di，则Ci=∑ Di。

（2）求N！一共多少位。设共有K位，则N！<B^K，∑ log（Ni）<K*log（B），K>∑ log（Ni）/ log（B）。

（3）陷阱：

①当N=0或1时，N！=1，在任意进制下zeros=0，digits=1；

②求digits值时用K=ceil（∑ log（Ni）/ log（B）），但当N！=B时，如N=5，B=120，用上式得出K=1，实际上N！=10（B进制下），此时zeros=1，digits=2。

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
    long long int n,i,j,k,zeros,digits,count;
    int b,A[10],B[10],C[10];
    double sum;
    while(cin>>n>>b)
    {
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        memset(C,0,sizeof(C));
        if(n==0||n==1)//N=0和1的情况
            cout<<"0 1"<<endl;
        else
        {
            i=b,count=0;//对B进行因式分解，各因子存入A，对应的阶数存入B
            for(j=2;;j++)
            {
                while(i%j==0&&i!=1)
                {
                    i/=j;
                    B[count]++;
                }
                if(B[count])
                {
                    A[count]=j;
                    count++;
                }
                if(i==1)
                    break;
            }
            for(k=2;k<=n;k++)//对2到N的各项按A中的因子进行分解，在Ci中得到N!对应Ai的阶数
            {
                i=k;
                for(j=0;j<count;j++)
                {
                    while(i%A[j]==0&&i!=1)
                    {
                        i/=A[j];
                        C[j]++;
                    }
                    if(i==1)
                        break;
                }
            }
            zeros=C[0]/B[0];//得到min(C[i]/B[i])
            for(i=1;i<count;i++)
                if(C[i]/B[i]<zeros)
                    zeros=C[i]/B[i];
            digits=0,sum=0;
            for(i=2;i<=n;i++)
                sum+=log(i);
            if(fabs(sum-log(b))<1e-6)//若sum==log(b)，即N！=B，则N！=10（B进制下），则digits=2
                digits=2;
            else
                digits=ceil(sum/log(b));
            cout<<zeros<<' '<<digits<<endl;
        }
    }
    return 0;
}

UVA - 10061 How many zero's and how many digits

相关推荐