題意：這道題開始是卡了很久的，題意是給定一個數(shù)n然后讓你求B進制下n！有多少個零，和有多少位數(shù)，咋一看，是高精度，如果數(shù)論不是很熟系。

思路：開始是直接拋棄高精度的一來是存不下，二來沒辦法短時間計算出來，所以，單純高精度是無法解題的，提題目就變成了如何使精度和運算降下來的問題了。通過觀察，比如10，為什么末尾有0，因為該數(shù)含有2*5，所以要想求有多少個零，只需要求n！能分解成多少個進制的問題了，等等這問題有點眼熟，在數(shù)學1專題里就做過一個和這個一模一樣的題目，因式分解求最小就完了。但是另一個問題隨即而來，求完了末尾0的個數(shù)，那n的階乘的位數(shù)該怎么求，這一點我就完全沒想到，后來找了網(wǎng)上的題解，才明白是怎么一回事，原來可以用對數(shù)來保存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() //打素數(shù)以及處理階乘
{
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));
}

總結(jié)

以上是生活随笔為你收集整理的uva 10061——How many zero\'s and how many digits ?的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。