uva 10061——How many zero\'s and how many digits ?-蒲公英云

uva 10061——How many zero\'s and how many digits ?

傷城~ 2022-08-09 13:49 123阅读 0赞

题意：这道题开始是卡了很久的，题意是给定一个数n然后让你求B进制下n！有多少个零，和有多少位数，咋一看，是高精度，如果数论不是很熟系。

思路：开始是直接抛弃高精度的一来是存不下，二来没办法短时间计算出来，所以，单纯高精度是无法解题的，提题目就变成了如何使精度和运算降下来的问题了。通过观察，比如10，为什么末尾有0，因为该数含有2*5，所以要想求有多少个零，只需要求n！能分解成多少个进制的问题了，等等这问题有点眼熟，在数学1专题里就做过一个和这个一模一样的题目，因式分解求最小就完了。但是另一个问题随即而来，求完了末尾0的个数，那n的阶乘的位数该怎么求，这一点我就完全没想到，后来找了网上的题解，才明白是怎么一回事，原来可以用对数来保存n的阶乘，然后直接打表计算即可（用斯特林公式可能会因为误差而wa）！

code：

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int M=0x7fffffff;
const int N=10010;
bool ft[N];
int prime[N],t=0;
double w[1<<20];
double ep=1e-8;
void init()  //打素数以及处理阶乘
{
    memset(ft,true,sizeof(ft));
    ft[0]=ft[1]=false;
    for (int i=2;i<N;i++)
    {
        if (!ft[i]) continue;
        prime[++t]=i;
        for (int j=2*i;j<N;j+=i)
            ft[j]=false;
    }
    w[0]=0;
    for (int i=1;i<(1<<20);i++)
        w[i]=w[i-1]+log(1.0*i);
}
int many0(int m, ll n)  //因式分解
{
    int i,j;
    int ans=M,p=1;
        while (m>1)
        {
            int ct=0;
            while (m%prime[p]==0)
            {
                ct++;
                m/=prime[p];
            }
            if (ct==0){p++; continue;}
            if (prime[p]>n){ans=0; break;}
            int nt=0;
             for (i=prime[p];i<=n;i*=prime[p])
                 nt+=n/i;
          ans=min(ans,nt/ct);
        }
    return ans;
}
int main()
{
    init();
    ll m;
    int n;
   while (cin>>m>>n)
        printf("%d %d\n",many0(n,m),(int)(w[m]/log(1.0*n)+1+ep));
}